/**2274. 不含特殊楼层的最大连续楼层数
 * https://leetcode.cn/problems/maximum-consecutive-floors-without-special-floors/description/?envType=daily-question&envId=2024-11-06
 */
namespace _2274 {
    function maxConsecutive(
        bottom: number,
        top: number,
        special: number[],
    ): number {
        special.sort((a, b) => a - b);
        let left = bottom;
        let right = special[0];
        let maxNum = right - left;
        for (let i = 1; i < special.length; i++) {
            left = special[i - 1] + 1;
            right = special[i];
            let n = right - left;
            maxNum = maxNum > n ? maxNum : n;
        }
        left = special[special.length - 1] + 1;
        right = top + 1;
        let n = right - left;
        maxNum = maxNum > n ? maxNum : n;
        return maxNum;
    }

    function maxConsecutive2(
        bottom: number,
        top: number,
        special: number[],
    ): number {
        let n = 0;
        let maxNum = 0;
        let lastI = 0;

        special.sort((a, b) => a - b);
        for (let i = bottom; i <= top; i++) {
            let b = false;
            if (i == special[lastI]) {
                lastI = lastI + 1;
                b = true;
            }
            if (b) {
                n = 0;
                continue;
            }
            n++;
            maxNum = maxNum < n ? n : maxNum;
        }
        return maxNum;
    }

    function test(bottom: number, top: number, special: number[]) {
        console.log(maxConsecutive(bottom, top, special));
    }

    test(2, 9, [4, 6]);
    test(6, 8, [7, 6, 8]);
    test(3, 15, [7, 9, 13]);

    test(
        1958,
        999841201,
        [
            765554480, 583627630, 751437502, 106114731, 535085011,
            992755060, 59244544, 727036824, 308076998, 183115302,
            264261152, 904951568, 613706966, 552621866, 242082807,
            804416398, 461877762, 490691143, 61376083, 357859969,
            938081226, 355288166, 548689555, 700280706, 450796293,
            105561113, 910009681, 76598197, 21040654, 672913707, 781143311,
            292241167, 782032918, 442917100, 949594956, 231683778,
            745890467, 199512907, 911654478, 715238346, 154699753,
            104594282, 57907314, 792021470, 296748068, 311173220, 76441217,
            749375367, 62032563, 840621071, 699040539, 111483723,
            721178232, 128004554, 503709396, 455793195, 872873138,
            763850860, 181131782, 32381763, 397044160, 212539880,
            669438685, 175423326, 879166551, 716956287, 163717556,
            548909133, 487640137, 133499269, 337340955, 788385668,
            232405822, 348322328, 368692237, 652799281, 446989698,
            955059147, 190695855, 421757953, 117961865, 593780952,
            940258218, 322671844, 36612616, 97270049, 156062310, 319323418,
            304097043, 931954954, 886087977, 468637464, 771198091,
            642396360, 706124499, 366927686, 718640076, 281127948,
            73301988, 404010894, 983483313, 845969010, 772980192,
            589368006, 561773750, 418878400, 145758096, 489138291,
            958188601, 701425676, 528768302, 115161154, 750872448,
            986047684, 506990862, 663279434, 387628162, 337179249,
            193224303, 17567885, 271767983, 1090620, 218770514, 754090366,
            313496203, 149906129, 87745936, 708791347, 703407962,
            274169946, 229243692, 75044347, 520607070, 684797684,
            337153610, 557381482, 26691661, 107415462, 337863999,
            530595462, 246452432, 106583818, 17338080, 722113632,
            635477847, 761399144, 6140305, 66623609, 242087221, 716467126,
            464006626, 997869276, 606410191, 968336533, 834009931,
            383651009, 927996771, 886437824, 630819961, 707020351,
            728325373, 45402423, 100521158, 404410796, 482723870,
            736021481, 614756740, 495790987, 51548321, 881850360,
            454068788, 118189335, 71435981, 537124367, 711702397,
            217253329, 859260864, 142101356, 944602440, 201172803,
            257639483, 972734543, 679737990, 98669896, 649003312,
            417881699, 4418541, 18537232, 389685275, 509148058, 642085051,
            946144615, 962875123, 547592377, 224292930, 692745324,
            428612927, 669852735, 945304424, 497199337, 554384560,
            954923899, 839443529, 95272176, 954776813, 840727871,
            968176721, 590374238, 277787117, 674628025, 302213362,
            945585888, 863774517, 669489454, 503958192, 241778108,
            942043395, 730913630, 92258758, 51398931, 593653587, 310140487,
            74662046, 494218445, 561906677, 729498759, 998210316,
            443400061, 662983638, 853935622, 820911233, 834822751,
            121571336, 259305593, 943371921, 128489832, 965595229,
            194626014, 340682443, 133843275, 99111754, 479800237,
            129775329, 465007683, 406575592, 935187724, 145954503,
            462292668, 564394728, 207247340, 103402125, 242161305,
            575982350, 545829220, 24423478, 222683160, 471190602,
            164546080, 580157667, 762376215, 385597568, 820220307,
            947799640, 915158509, 885968961, 406370501, 677240175,
            996856961, 501978816, 828852381, 943908240, 178813452,
            701269218, 60501532, 391741638, 658742898, 836007789,
            659567436, 76985350, 776371374, 788067449, 504745989,
            226577819, 971824466, 667807332, 722221795, 499861221,
            408968279, 483367456, 78791543, 297646176, 593250970,
            723754901, 420481618, 259030839, 16219733, 533284118,
            137955037, 551345085, 264977212, 205825328, 395836212,
            499922639, 252208832, 936335087, 725203217, 992220109,
            574098946, 415056637, 306436236, 698156555, 613602324,
            953334963, 966309464, 365708675, 876257220, 121021453,
            379308891, 534384023, 104083478, 886095990, 775165309,
            471425501, 906870442, 123932127, 218683184, 895208809,
            218907710, 351145810, 446473734, 889140701, 113493692,
            655815077, 149538595, 177623832, 316561332, 407401037,
            278936081, 945161677, 2604889, 900580910, 213373945, 47310305,
            161843247, 294818310, 605135222, 27428440, 902569426,
            156422841, 96062280, 553196470, 559180262, 393613273,
            154219417, 30168347, 583195096, 842156826, 973730726,
            440412004, 270361079, 15956881, 845897517, 503700995,
            142804607, 533145485, 972055797, 211725316, 715213483,
            354069943, 201314105, 379754892, 121989725, 212845198,
            928753965, 841234417, 341147381, 648185094, 642441811,
            630752541, 287192175, 384633971, 231569557, 302590252,
            125683991, 899166349, 99147244, 916209497, 373647028,
            813420921, 88725006, 338229679, 899417074, 488169642,
            785359137, 520752043, 413322941, 421664414, 321740521,
            872112382, 996575710, 306204451, 659008194, 187939667,
            948878375, 565760229, 947965288, 41869976, 89000137, 704989357,
            185330680, 711267047, 487723326, 966772693, 394537498,
            356690462, 248921635, 775590613, 411139054, 447880668,
            954614421, 101678571, 652462757, 782443148, 742557950,
            585007651, 824073514, 580076662, 162131180, 335052617,
            504847974, 153446631, 25636399, 422603243, 108430430,
            106348697, 908705315, 782496984, 21974205, 951964621,
            890129935, 549514945, 988784414, 393526762, 120298137,
            479273327, 200255806, 123988898, 916075466, 550159903,
            539547172, 467157288, 79940511, 423147560, 72249581, 312985549,
            467041157, 89069878, 307252502, 142158185, 109034905,
            845031587, 380652229, 46144784, 404020577, 384114710,
            466740233, 752946427, 415299139, 260535789, 186209165,
            723069276, 437797293, 541570964, 270122129, 771722036,
            956121727, 463964881, 361698351, 750655683, 178330409,
            409128126, 987878652, 529153691, 929876873, 314023356,
            145468352, 147198334, 504090846, 758489385, 852407969,
            649217890, 313512114, 288582504, 454436950, 856225024,
            772870119, 951136947, 840576529, 153728204, 116374161,
            407789479, 508839359, 676698758, 934113799, 850971758,
            323369676, 840582186, 990970126, 129739919, 806487931,
            351203459, 83624271, 963151373, 423187147, 121119185,
            782863651, 496959088, 446394308, 68698375, 172210661,
            516729707, 182128724, 796114093, 567925181, 626488816,
            678954346, 161891456, 250419105, 238962387, 18524645, 48218220,
            563562994, 146306670, 222856895, 256480899, 191590442,
            934118383, 452647078, 510707222, 466814586, 432078601,
            743481219, 580670880, 569234494, 260439167, 524360476,
            393055883, 393383504, 597204640, 213081302, 353698577,
            48780015, 37493246, 263061372, 914928374, 750056538, 379752185,
            365039802, 799451783, 659367693, 391832030, 617256625,
            487083395, 717479199, 476516846, 148188234, 384067985,
            382572126, 76072461, 693095289, 416912349, 37391415, 673933882,
            752244997, 759183774, 983710085, 839513002, 125623055,
            554859975, 548651212, 289153360, 738713, 757294703, 402808818,
            247066210, 82720796, 558101317, 714844706, 39045876, 715244086,
            653308428, 639802819, 653219436, 888501203, 748541300,
            136519634, 457790714, 764803162, 517028355, 133986592,
            485718959, 272358506, 306125048, 245912955, 841723863,
            640458426, 820996466, 36180119, 502533789, 293329164,
            553055657, 34272048, 452372103, 424603593, 647411362,
            815452972, 784105618, 369768978, 878161017, 100954462,
            942463326, 41570379, 785836274, 299484329, 657923666,
            262268303, 121128609, 681418501, 915862884, 929846469,
            344689983, 443514553, 959905747, 696334503, 228248475,
            34366167, 492421967, 442635551, 481045859, 20160576, 475967010,
            247532048, 782520539, 842727320, 253251268, 670975176,
            262061257, 615488555, 230742222, 192025624, 645041531,
            695295184, 975249984, 316055525, 407748313, 561858348,
            502207920, 138995850, 509263248, 983834617, 633325236,
            950588961, 690647611, 330662003, 480981539, 245218462,
            574777452, 74061042, 728538210, 322602616, 690548629,
            362764233, 166142055, 810933249, 175015142, 459478957,
            915993917, 41456866, 75430494, 687516848, 790917103, 855998183,
            220697778, 119029474, 994547592, 979963109, 449717363,
            269235560, 697400547, 819183011, 204132429, 899109067,
            272798051, 357308257, 201971950, 428126430, 413488573,
            968264250, 941172020, 39818836, 987680664, 837633679,
            563508414, 970501507, 604909470, 307725549, 885943503,
            813751519, 580687972, 991405605, 29045939, 684950766, 59066362,
            38349767, 429421646, 277043637, 620726818, 760744646,
            433793991, 492009663, 518242787, 174502062, 446607063,
            177183812, 997519474, 119381079, 50151606, 841659518,
            990890474, 7783369, 815517926, 945591315, 156964068, 77858547,
            765586340, 920567637, 986800890, 198136026, 346045555,
            301193530, 130031299, 556772500, 13858605, 62078400, 463079844,
            837347151, 419985419, 875022112, 554984635, 720177389,
            22498451, 304500101, 573958458, 279562017, 230147242,
            723316229, 239524679, 930981536, 731964161, 395424175,
            852745666, 988840032, 222673383, 439490, 83924900, 198561364,
            284682913, 137552459, 721017258, 410575387, 399247144,
            785344142, 636976645, 273114710, 840273902, 669199705,
            194202172, 535989547, 498877774, 207147716, 15194832,
            265052500, 94048166, 260111563, 431816478, 978001433,
            799316534, 741411416, 578540931, 697096584, 419165039,
            130007997, 350964647, 859003211, 145164078, 265967609,
            157055627, 925688884, 946962840, 583871122, 69915563,
            212027204, 210086148, 21742561, 205787429, 903266048,
            591486042, 174213271, 495737529, 931351215, 562308103,
            734686901, 283097980, 886124523, 947476070, 248378203,
            618990505, 294059000, 768312650, 249714220, 975805534,
            354003559, 929882084, 519546051, 398384172, 322908236,
            960399081, 435061407, 605044513, 135914967, 561907467,
            210111651, 912276966, 720918562, 704507229, 26728885,
            349809672, 336687150, 211231125, 583419628, 303731747,
            720068033, 477847521, 412245265, 542861911, 364605155,
            531498750, 856356288, 406799495, 139536969, 498360091,
            93649642, 136641718, 966447674, 277477181, 105278689,
            149519154, 317183494, 527299162, 484548604, 960853571, 2437843,
            432527742, 533578103, 949804522, 295404098, 400846909,
            174509451, 501627776, 1855356, 803911609, 568246947, 528824453,
            25045425, 234963657, 990121053, 534606533, 227786272,
            911692398, 730052474, 132039128, 708787895, 384836113,
            283818646, 424674662, 227602901, 212745961, 418604217,
            667763580, 236114700, 934131861, 747150806, 286315860,
            78281507, 147542330, 186415626, 196249383, 375472407, 55866500,
            88719962, 125811083, 347686515, 61431953, 237447226, 528386183,
            797977787, 630122627, 390858607, 170590395, 903566335,
            300648927, 459829223, 825777282, 434678984, 73519367,
            776641962, 160813520, 745177762, 962805917, 132712310,
            988904806, 547977684, 564119656, 364550029, 923918098,
            204699980, 44720679, 397358472, 434540188, 39708556, 978510043,
            498929247, 994395374, 298585264, 680949448, 633835050,
            130955289, 479891764, 393865963, 268837665, 113040867,
            17255184, 556716079, 344339940, 531896450, 456036401,
            326507203, 44292683, 616399537, 777050494, 572317596,
            249474549, 96022694, 768318682, 851873553, 193176565,
            105643094, 147095795, 549208871, 632894826, 352127284,
            995926764, 502940283, 476002866, 425697265, 666548265,
            148374121, 153626061, 445757050, 831719194, 55697155,
            395446722, 890854997, 3022847, 748956907, 5670083, 873091186,
            931019491, 772220023, 305872078, 434718399, 648544366,
            785959860, 498264723, 77170702, 438454228, 436179273,
            510070273, 775721806, 616028437, 581587511, 845540835,
            173047598, 684178012, 512881127, 480152544, 437263058,
            457046383, 150161741, 34648259, 321170650, 950007947,
            179876986, 214884482, 50171907, 381575254, 412477651,
            831792597, 495915708, 231374896, 558451174, 617580386,
            280353563, 808713791, 192934760, 145836805, 255803217,
            809505247, 263323606, 591532099, 223599204, 758238112,
            892113186, 255536402, 763232681, 827766663, 598477783,
            563091643, 541513992, 65853875, 584294040, 266115871,
            102114432, 338935642, 35843489, 210349491, 43387108, 493153518,
            142986739, 232818407, 804411096, 662498382, 941045865,
            345904588, 314849172, 928656280, 455801975, 505383333,
            411520261, 347083406, 807497472, 442692208, 302509626,
            434446774, 346898612, 613310466, 9844499, 239975237, 585460229,
            341824445, 495691131, 489689053, 710635387, 716717736,
            136356118, 185497601, 671813171, 680686563, 909981028,
            604245051, 835657569, 271152461, 358787859, 925440658,
            313526320, 639490662, 437121741, 553796317, 629230100,
            888054951, 262735337, 578944331, 168343244, 598999438,
            897730164, 866321036, 22020975, 539185136, 856742312,
            536437949, 88761825, 761986360, 412108360, 7796977, 937054682,
            199244734, 387402020, 838347000, 398429279, 329444419,
            894130835, 418815199, 373899137, 795741069, 747295153,
            32382136, 320917442, 591741888, 14962951, 666369151, 8308510,
            801845591, 734740728, 896059033, 664377560, 395582502,
            979346376, 654614654, 865908392, 53232359, 607655061,
            305354403, 416304827, 404527505, 715657309, 18058881,
            499278565, 888292822, 451702049, 876411981, 260098461,
            520474990, 648729244, 423707481, 495666496, 322585896,
            674934958, 164131308, 556847380, 139683086, 18291223,
            212842242, 907677582, 78894711, 728101153, 977330102,
            589593995, 512361401, 522245529, 719203904, 795175984,
            32931597, 367099099, 856661, 404766771, 193062614, 786441609,
            247844296, 362155409, 767156863, 912713069, 662049205,
            622554466, 537959642, 160734075, 713692915, 88174664,
            759684899, 175221856, 756283286, 165218175, 167492929,
            213180599, 119122080, 24109222, 864684674, 164394435, 18178917,
            408276343, 512038346, 997457734, 95572364, 113443765,
            220098075, 852659563, 256476750, 175923439, 925352120,
            972615548, 510421674, 588622009, 66444623, 453769737,
            867730955, 170951766, 794033744, 445034880, 357766318,
            241766943, 793431919, 6197431, 285346727, 388025189, 971559005,
            18123005, 106513418, 609766459, 404168740, 111194926,
            912821357, 885398594, 75554598, 709340727, 171415765, 66685892,
            344872866, 314175145, 93662490, 756219921, 671342601,
            125820034, 836502279, 865001417, 192831470, 575669098,
            416127081, 840729577, 186366090, 960232342, 896157580,
            145311145, 713865405, 278038437, 85829760, 997587916,
            948749502, 43475281, 903398981, 714709083, 182759852,
            930634020, 7376356, 379063958, 542831295, 481356088, 117054410,
            171949062, 976967643, 59090901, 276555278, 393565503,
            351580602, 228692241, 361594803, 367701507, 84307989,
            188101647, 515817022, 129426115, 396929827, 491461809,
            375863564, 142153371, 250818725, 692158376, 892941720,
            573109185, 23060384, 452349679, 661540428, 622157923,
            313415601, 551377404, 285862354, 864332036, 263851590,
            50438084, 505610106, 431852585, 227936959, 476503369,
            178925352, 3586541, 751978697, 983732150, 419356630, 64021777,
            466880140, 411551991, 175874658, 519387360, 299206793,
            291932606, 586352228, 697443084, 33793816, 989187576,
            500298047, 930114407, 684178981, 794014129, 794911158,
            287568513, 751560236, 390577588, 535656802, 837311722,
            895507653, 429568825, 707644483, 875544736, 329163506,
            857291595, 216297975, 305505621, 632969881, 81006966,
            592966402, 325910177, 474291760, 233641622, 708294486,
            949294121, 613052854, 493089589, 148880781, 142841307,
            236311867, 235264632, 538412506, 731093263, 333084157,
            313851171, 803889378, 338169552, 916247227, 286627069,
            535155989, 411680626, 445651204, 340982473, 237246498,
            652240117, 35486484, 861163947, 933561241, 919190635,
            797358769, 691176331, 448875323, 470762014, 119573778,
            168035470, 17334680, 512971118, 639781556, 326350068,
            492306439, 437087451, 213989300, 958440249, 974981572,
            270707378, 854980908, 594566970, 635689874, 721959513,
            432029769, 383708606, 28525866, 447410154, 158606168,
            278897039, 951443542, 439047520, 157310606, 854689240,
            827833954, 152118206, 46875988, 508831047, 673392008,
            500682266, 601150918, 988048514, 102851118, 654048116,
            562831368, 84703568, 847964832, 540854725, 737530986,
            807822197, 697568747, 622833749, 400480026, 843005543,
            478707747, 715132674, 653193910, 276494860, 215880806,
            864532912, 359096318, 882192375, 87750269, 802970677,
            496604487, 397190154, 588744136, 350463351, 138971682,
            95727039, 990438125, 275504142, 823935087, 583471486,
            429809979, 237342920, 508515822, 663633074, 810503381,
            181024410, 145213714, 458330431, 450918055, 142467969,
            623949692, 740868112, 219952370, 204946105, 957589103,
            618872080, 388934023, 389503504, 918196168, 282730194,
            230080184, 300785092, 219642618, 955010592, 408072572,
            208058446, 502442634, 534006960, 537469284, 928072562,
            463437842, 85428987, 320592624, 801688611, 438073821,
            966712756, 725943154, 248372551, 903002596, 481959617,
            504063138, 15518111, 739765161, 281693926, 559283294,
            191398711, 516766812, 460472253, 365794484, 932350041,
            731478407, 212506674, 484658478, 794287185, 673488377,
            298025055, 520481905, 469943354, 301533745, 371344163,
            74602377, 912179133, 397495276, 566716942, 270601211,
            944828356, 314139591, 221365716, 470290304, 912084407,
            61360657, 714952035, 780591741, 285519559, 529389761,
            498670696, 870823982, 44881001, 909154444, 397110133,
            857606258, 266087688, 358856832, 272975068, 899626571,
            911877766, 773114495, 340688433, 150273206, 93537045,
            136183983, 75763940, 904894896, 478735224, 876097992,
            686158553, 870952215, 180756847, 770251143, 458874688,
            662902233, 477707186, 870861785, 647462052, 834877919, 299733,
            763037088, 950856570, 464190784, 560595408, 504563555,
            76504194, 621370582, 206363304, 872524381, 146812527, 42464940,
            852645182, 735011721, 911988819, 654077867, 170587676,
            279570385, 248166453, 717602577, 603232627, 327524035,
            95685308, 286279888, 71007311, 582828999, 885115495, 251777965,
            9424499, 842224041, 895376246, 827418264, 740116041, 407406889,
            417464960, 814209320, 82840829, 238157863, 664334571, 40010340,
            272137778, 840258061, 69625447, 496869805, 610720227,
            770235535, 258095917, 411677862, 738607305, 270552782,
            365665163, 457486186, 110884091, 766987824, 343213214,
            402887401, 540225340, 16244644, 97378639, 125085932, 151044568,
            267331760, 707552277, 453278953, 717971690, 35077148, 83881674,
            29848283, 636637366, 317526530, 561728324, 775150683,
            752144957, 970498103, 971385477, 265660631, 812438790,
            468896202, 967308203, 164874137, 691650173, 180154279,
            907662874, 956157790, 835760443, 508420915, 581340840,
            677344647, 762753754, 816015012, 59800271, 552312854,
            240042037, 887984173, 437423301, 663471242, 365769761,
            900080359, 948336318, 700784151, 8174649, 264868874, 353189423,
            482909562, 476232594, 173511477, 140703205, 57231380,
            553690715, 134718028, 938842703, 245491932, 426064557,
            303432910, 489398380, 523858021, 562420183, 176713032,
            568898013, 283232630, 743233646, 730096117, 403010477,
            609017525, 487788122, 377417135, 345338276, 435381414,
            50955088, 827373716, 230519265, 462157064, 639855550,
            211261673, 97712507, 876242729, 884304012, 126140487,
            791912221, 314453011, 869975986, 783925786, 496747052,
            595981101, 825031116, 69566852, 623997490, 44942818, 875326705,
            573061339, 260150617, 583729679, 530661175, 536298804,
            590191903, 921191878, 636312056, 553911427, 346824738,
            181000904, 663566443, 654529976, 680499151, 428720886,
            273598993, 238667364, 38535689, 207997951, 508361543,
            701445069, 384437844, 600197628, 19286867, 79440424, 439310259,
            939735764, 547150579, 600223146, 374801771, 128046396,
            745357842, 373432775, 236652762, 212115425, 59128473,
            414945712, 365635129, 426712198, 32918704, 638375698,
            817136354, 930896496, 827795913, 601032475, 880658775,
            702524099, 761192999, 164849140, 222262163, 765031292,
            645989856, 798100418, 128278622, 97060335, 691219128,
            759773221, 378776835, 712960205, 702378650, 521082391,
            743912623, 237184934, 618062422, 242034793, 304516571,
            263136081, 149823125, 201538143, 288089165, 627064920,
            811973373, 873877677, 458636927, 53317908, 713734872,
            785875465, 945879905, 860765497, 331754740, 805519314,
            869512675, 509595409, 279385491, 277149895, 115527898,
            85867031, 190519782, 497928769, 849931714, 296726569,
            571333002, 287639293, 198681170, 204927953, 971034942,
            516887270, 294563746, 873850568, 241694140, 925318285,
            387725112, 655573986, 363412512, 571868219, 781586282,
            841303798, 226961748, 708988798, 935836588, 387589297,
            655984254, 662015964, 664421922, 644618334, 496380383,
            43111665, 587147143, 481495620, 36583300, 170063371, 698403112,
            138527247, 754775689, 113503198, 219995522, 696601000,
            535859951, 966016275, 51532381, 749518804, 719831625,
            374211115, 585128661, 950146395, 638156330, 728532181,
            630659984, 616321169, 702219815, 852742911, 114627536,
            285064706, 437418120, 480065749, 588698291, 849362837,
            588553572, 889432590, 494018626, 30467103, 886598081,
            225471276, 886031944, 966970689, 22809412, 384105571,
            940222266, 359163607, 99004457, 39350993, 983123082, 283959279,
            423110760, 308820816, 904096853, 57322516, 939833847, 82520942,
            853253346, 633086156, 126836440, 213104198, 952823419,
            739501186, 158992369, 541795433, 443378988, 334322150,
            64832907, 33561422, 777486698, 690066597, 736704601, 298878166,
            283996185, 976583093, 498729665, 456970252, 129464968,
            562539007, 598385653, 417613706, 887780094, 534104351,
            873230752, 865150604, 987064985, 936873763, 442458996,
            718283582, 185554896, 143888358, 865329287, 9370054, 520414595,
            913324885, 794164912, 382018842, 317420486, 146232361,
            745294584, 383793420, 814172975, 91680515, 708921045,
            401125262, 866843977, 802396885, 702477855, 175494361,
            952777057, 573252389, 151292361, 846513455, 940686733,
            988956964, 75988508, 564992338, 469220338, 401335635,
            209406560, 345939486, 761871477, 549679943, 270667344,
            665554061, 64244538, 914601744, 950916123, 551444787,
            153814872, 472066931, 347751855, 399587722, 779217677,
            283698782, 10915783, 833781052, 981899390, 707938570,
            381334702, 914122612, 757363777, 235851709, 978618786,
            119430712, 188664623, 905440751, 959331529, 171218421,
            390133014, 635388414, 183347612, 585394702, 104746280,
            488465932, 17184935, 164285459, 997928175, 325261498,
            995797694, 451887712, 874282955, 447329940, 520484521,
            880666635, 820462870, 809091649, 937441793, 490303476,
            318069572, 372132882, 541422891, 443738758, 576529796,
            180624524, 117196000, 203302684, 613948950, 826835014,
            932231312, 791757657, 296846574, 944727250, 984754252,
            831475947, 135667948, 404631694, 610669187, 397851156,
            829813073, 645112740, 474389701, 839606160, 96436303,
            484064766, 80065626, 21606277, 56035581, 76197955, 206762714,
            798246017, 400407091, 312504580, 970342713, 114538155,
            774900766, 585922480, 692100010, 677923925, 776087686,
            560859818, 399168690, 801776906, 59302325, 342023751,
            769892738, 924752071, 506750914, 486966794, 85761500, 9150307,
            764950178, 641568474, 948481452, 480467182, 538087771,
            59632273, 882256279, 295359475, 362994774, 830050017,
            157318218, 572686458, 36236869, 363736501, 319049302,
            774073075, 912583349, 988188396, 39765318, 804177113,
            337089599, 715637531, 32328994, 740718588, 513894993,
            812511340, 980215320, 514669987, 178824865, 696373494,
            306114923, 705592352, 494493668, 368558005, 598104875,
            794607842, 512396659, 608413102, 853471429, 823344757,
            711242862, 958900240, 134418085, 486560701, 524441308,
            55256380, 890460169, 649763199, 610864066, 342603169,
            107009885, 607237050, 715034940, 894254104, 950943741,
            546701438, 668255461, 72043726, 653730881, 341191761,
            117437438, 814976286, 385889622, 282343643, 949178960,
            484315554, 883252466, 943010877, 432799093, 791086725,
            821334416, 409952294, 674520742, 533115748, 258551614,
            677851339, 112823957, 367753815, 37375166, 395230420,
            460971778, 586579415, 879164673, 827394813, 666093627,
            684773041, 127766301, 193691585, 571926155, 116063817,
            552079667, 9872107, 305871423, 720732996, 394612582, 771786078,
            110509761, 238551211, 209724927, 558812391, 317768348,
            276750772, 4787094, 134646862, 933169595, 349748859, 641938757,
            395548729, 557174819, 25059000, 287188494, 898934133,
            929232838, 201344969, 932689633, 811236794, 471211210,
            648625588, 792917546, 135271041, 31766418, 38348278, 329228635,
            743985126, 636305322, 738478718, 762825721, 517743457,
            106570255, 47715711, 270827559, 41667156, 798941850, 155859847,
            593283464, 145824736, 970920594, 685055191, 513241783,
            21294055, 286327209, 669627947, 221670106, 232202795,
            624562033, 332386367, 61950389, 511580042, 824735089,
            967068436, 300418445, 575898803, 937938944, 206250724, 2946002,
            321480145, 268135428, 817178508, 143725297, 8730686, 995804328,
            328946844, 202606104, 911029129, 782557259, 892470076,
            850287820, 860170410, 761190426, 454566885, 303351202,
            600744128, 840330217, 848304478, 99514911, 522061105,
            503407781, 555052355, 479648089, 19577789, 168528694,
            154713854, 164310339, 442738750, 460193850, 331383053,
            469236555, 669617779, 542218178, 661631751, 682023978,
            358500969, 737595613, 336518118, 824852261, 369338803,
            191798693, 757532382, 346863899, 657056119, 321767351,
            954554836, 142459042, 66400994, 521743740, 506477434,
            151153046, 7960073, 752306248, 58839823, 156576991, 987600109,
            385905954, 583109805, 714967644, 581277237, 248884957,
            661296689, 36415347, 26948179, 121167048, 266743920, 673260376,
            695027969, 92557545, 124187955, 167054121, 353677731,
            158370341, 760317071, 760245374, 747778004, 783751958,
            541393985, 573891939, 851894396, 724219834, 313421120,
            193085535, 816956320, 553604977, 946888754, 751650870,
            34020699, 4784086, 186142130, 607010932, 173340302, 882395459,
            94121039, 498813186, 299567086, 31774979, 316011903, 474804212,
            66065583, 810951976, 67823255, 706730458, 271482885, 105763408,
            627743057, 993072938, 366037205, 786661840, 606548418,
            621303962, 922956442, 298870266, 347588209, 561243614,
            269455697, 113437001, 157100548, 787643028, 877596439,
            270202034, 389737653, 106428295, 237315606, 508897904,
            293060830, 545675054, 621997504, 1819676, 384140676, 335695963,
            137832771, 40862741, 319729445, 118673192, 937237509,
            422777572, 817569025, 11670390, 767034170, 863042270, 5868807,
            918301079, 372537804, 191610249, 185096217, 834575728,
            644065294, 433327841, 510573049, 565693869, 190904020,
            532918496, 254745425, 504296877, 850537675, 644123882,
            900339250, 862917780, 456256812, 850244993, 131452980,
            741462619, 598273743, 312854913, 366099063, 646811146,
            440069055, 502770173, 673727282, 167452210, 811715353,
            245326195, 723375579, 115772401, 510826035, 959857613,
            46791087, 288989148, 451291122, 220748269, 689123581,
            694541356, 315509703, 117532175, 243260787, 143134609,
            140157172, 896848387, 213233462, 733442171, 872620313,
            730842318, 559116842, 999036744, 244411259, 725379098,
            429555393, 453386562, 15622648, 951427850, 373126514,
            473709439, 701086240, 940732299, 728428116, 651878159,
            432374144, 61823837, 831539198, 464497887, 82813507, 25328984,
            543329316, 313417666, 6029802, 175980849, 230634117, 141636873,
            520245615, 84329049, 33838616, 115869396, 889118884, 361304841,
            643159386, 599801430, 940619635, 370390110, 864374284,
            137026496, 751071965, 545074175, 475117124, 927903084,
            821340184, 257677309, 380620282, 974889877, 404610872,
            923336285, 54611592, 915029968, 899583778, 758779283,
            466326258, 636924871, 747798287, 781200158, 811710830,
            989801450, 412320388, 231277209, 585920845, 894374751,
            215901734, 217044209, 111866192, 920561449, 222915168,
            179152284, 916978842, 958019902, 208712579, 71016289,
            674460276, 247605376, 516431556, 365117341, 874326853,
            862804758, 384273978, 87208122, 731447626, 933593668,
            459474934, 862859678, 355466078, 825118290, 916904018,
            433518341, 349579988, 663185891, 82525831, 82674972, 427806176,
            99893365, 916905700, 791508135, 6176914, 390688819, 818912240,
            151494440, 224537112, 339984845, 883797661, 510030261,
            756239906, 562799074, 421743850, 158011236, 874297875,
            661265057, 465427745, 359196707, 642755759, 616126738,
            888408532, 1484175, 134471027, 77114588, 855154698, 226964806,
            271880198, 8603224, 17708824, 399623165, 962747200, 532153411,
            276147379, 231470833, 6375899, 200816883, 170106769, 832716878,
            270207900, 898571488, 283036816, 372066589, 895794499,
            954769860, 447086059, 285678266, 571463523, 282274009,
            32800580, 356794724, 57982811, 802403780, 49976888, 98618625,
            751890319, 801800304, 423778149, 642355364, 672740945,
            842146709, 671215719, 734628537, 948374429, 825824888,
            827584105, 104286762, 833204991, 237389050, 281051519,
            492963966, 215189538, 651670577, 574136772, 986350266,
            161345303, 49893733, 761185581, 623529577, 707714372,
            389443308, 623025306, 138858525, 299430328, 138817879,
            260575808, 905426098, 526772067, 693596158, 634941609,
            572653661, 347040542, 955977901, 554453273, 768238537,
            465862945, 13183539, 301191119, 271492041, 113799070,
            876752499, 114403721, 860779277, 89432513, 874677707,
            584991085, 581508794, 155538619, 474827532, 705312348,
            108346028, 371101786, 854416094, 694915781, 894391116,
            966084604, 711999462, 935872946, 217741964, 127572722,
            406517358, 53353850, 924122005, 581576779, 737922695,
            537258535, 283129200, 131680305, 650606030, 702402245,
            787690909, 197697435, 129455730, 518148535, 685614875,
            205328318, 238053039, 70988098, 319306458, 83068664, 767488406,
            771819341, 541789235, 13770801, 22970443, 182126858, 293094124,
            652557978, 276358481, 772163726, 193529740, 595398555,
            103651662, 729875643, 39071811, 716549488, 315352249,
            179406944, 149754110, 886422040, 960356927, 90051537,
            390756470, 497040094, 720761932, 302964940, 679005983,
            26969226, 882856929, 778536699, 734267783, 74762398, 718295890,
            188122446, 585623867, 140042612, 305023885, 65198864,
            475811812, 660713432, 94322789, 367378570, 539830742,
            657550123, 945680253, 622525628, 919921721, 330047588,
            218524258, 947414083, 872582902, 629336233, 25255802,
            152813533, 65332784, 803737761, 261463251, 272999619,
            802880047, 180826278, 28308142, 771993271, 198685308,
            249831017, 792754468, 164097866, 196522863, 416000492,
            850092996, 132499493, 890344898, 822498093, 190431508,
            879939473, 464115782, 196313017, 699417434, 351948735,
            687957736, 942474139, 319956440, 91669514, 316830639,
            668824107, 705101253, 472220000, 416585399, 458711576,
            165255683, 365852282, 266666237, 342195433, 697614501,
            338888690, 27635234, 333767410, 602076174, 337816869,
            857734579, 636725626, 621782946, 580958317, 425044013,
            101264192, 463734501, 830523867, 676355492, 399197546,
            968591529, 572730639, 897894482, 615099454, 182005860,
            35996190, 717413179, 186239016, 14547091, 559949915, 480613694,
            778437723, 274271380, 486345871, 11391128, 536455252,
            658145175, 606516090, 730824031, 845970960, 179682200,
            746793814, 687182583, 568115208, 660497010, 745531383,
            914919019, 430391065, 460760427, 323229684, 805634614,
            280366844, 44818546, 712401731, 455346500, 556450213,
            295171963, 262630567, 968289353, 732001103, 750532360,
            252063429, 529746167, 939861794, 240885919, 630664806,
            818913090, 278795752, 475351710, 611664941, 962996731,
            485760332, 506867360, 91580763, 650077202, 889271319,
            332988794, 144786979, 70533828, 379721063, 791595363,
            767259924, 822383267, 778164979, 484457421, 486356993,
            822220609, 474195364, 215880701, 882796059, 813586827,
            344452140, 365475241, 504790205, 466498855, 664014147,
            419455388, 183481996, 884102261, 708884237, 985903850,
            595968914, 200817396, 70897998, 230312252, 90800972, 355022957,
            457083192, 21873667, 885089055, 272522441, 417688891,
            980980156, 873872183, 544730142, 516403726, 334729059,
            608284838, 29902809, 796805663, 235088795, 665288604, 62794180,
            726492504, 351586980, 972599950, 295458064, 957259869,
            336112134, 450750266, 384177633, 386412331, 219473812, 3698889,
            979940313, 636535591, 831246474, 992347034, 735321030,
            784882698, 825054031, 196780484, 681491735, 587384278,
            554752270, 111375318, 198214959, 572479529, 776165905,
            607950613, 374524974, 722682146, 376887878, 370128514,
            281522045, 814387737, 845489306, 773493920, 651590731,
            715536990, 318947930, 841408281, 979572087, 181932478,
            728884191, 753205586, 965464262, 615047755, 182370377,
            804471336, 203045124, 262719646, 667681574, 88632074,
            766069770, 231834210, 482185700, 74733742, 944683186,
            686493614, 608724024, 314412924, 830993040, 168384386,
            916773849, 95505676, 538250246, 565207404, 326469556,
            625204209, 627048198, 938765836, 145622167, 881218056,
            998343902, 144391869, 637782617, 880990569, 430455029,
            456401419, 866097016, 240591895, 222802264, 816706046,
            793850365, 34011871, 270293735, 332722912, 460413230,
            452942191, 927977045, 788983876, 8166271, 908301267, 808016897,
            386615821, 980915214, 428835866, 475305383, 135698197,
            146472820, 619310392, 428800617, 570643269, 410340534,
            648794627, 157172855, 83996264, 691462047, 633227656,
            750726483, 406644660, 521788711, 60241952, 684355873,
            623390395, 529746637, 357459504, 751729461, 350080327,
            64466904, 171099073, 241331611, 932561273, 996117987,
            288459322, 24575680, 574958871, 850175028, 858745639,
            688372408, 165335865, 598491025, 770248535, 947329715,
            509587285, 390713747, 911730788, 502109778, 592934304,
            602401076, 14907763, 270497910, 112534204, 534808359, 84363491,
            625511422, 976793663, 797593998, 195528032, 438378919,
            899747053, 544073210, 647524638, 985607525, 81779354,
            894943847, 643519588, 676060144, 250168973, 887761088,
            560607790, 597230119, 549933692, 313072623, 729857592,
            978651442, 770279353, 277031057, 852724349, 205152212,
            630680304, 432725588, 142726466, 107810893, 841486964,
            209333463, 371049663, 608111062, 39297179, 314568678, 20574737,
            809083311, 849932789, 745295078, 61804254, 431779324,
            858588923, 80578190, 745259453, 747058784, 480551072,
            579126225, 72232653, 279451870, 501472608, 181545999, 26701885,
            163899700, 251810975, 991481294, 630638901, 528744634,
            742998778, 578500559, 987109770, 218250040, 76795401,
            510536241, 386322994, 963517105, 398399402, 839515279,
            178064372, 434924768, 654407228, 551639053, 380592547,
            379481798, 231412964, 364562177, 251909666, 618719740,
            95771998, 849692819, 438725736, 156703568, 541868968,
            578491806, 118892959, 246612809, 151431091, 59345886,
            529730707, 122126989, 971967352, 893280468, 346157315,
            521122480, 17766734, 829592779, 73620961, 916115933, 869128937,
            567444492, 850849703, 43991368, 487437691, 606342299,
            501277233, 497357518, 298376122, 786618965, 620325037,
            712988265, 554516902, 832777177, 555992907, 275253881,
            903665356, 486316518, 663368826, 150982226, 310462445,
            208073949, 218485683, 719323860, 17794914, 800581087, 85295460,
            16603025, 419466040, 532150341, 10771707, 986516147, 949426947,
            536212848, 777074091, 592367650, 388920058, 670496962,
            654448254, 159701266, 7206169, 952854912, 351928962, 855352758,
            949640674, 310343108, 961009331, 5028552, 990894467, 421816636,
            265673605, 814801189, 833110070, 717792363, 52497297,
            647641469, 911381329, 777292294, 837754592, 592416834,
            710810703, 28600233, 707811705, 727044977, 43110787, 256150423,
            222554172, 111637633, 795517630, 957736081, 193376009,
            250234459, 470965792, 652549326, 691346018, 461245823,
            293029968, 390743586, 249800244, 274543220, 998207967,
            383689748, 443795964, 494201967, 408775180, 310471670,
            149721983, 520934918, 506000592, 972041890, 703990599,
            645778846, 53031465, 551607045, 845552391, 584029089,
            941441043, 683566905, 187441547, 728700206, 221253424,
            841598385, 401902846, 990367251, 885008837, 326467685,
            861533408, 909952084, 626053868, 50778836, 919353332,
            957235248, 676819751, 563409178, 228598392, 933258940,
            725285702, 883598305, 706133724, 411627926, 587219341,
            818271923, 73504446, 238547763, 726221378, 767113232, 55440573,
            457745622, 831894139, 180152875, 148158708, 846001928,
            323703854, 582900023, 996409339, 636619165, 70420873,
            172846685, 47760098, 527755788, 824953908, 88366237, 847728939,
            843461615, 880728053, 224136355, 739527442, 709182205, 4345245,
            106824927, 900495357, 122189951, 690103297, 48181997,
            968927026, 808711187, 948379480, 947518005, 619374350,
            65984767, 996121723, 999461869, 459991723, 546637906,
            574749705, 529630386, 74828168, 978125309, 703567458,
            926814690, 115074013, 296267878, 801119398, 926134194,
            66359655, 74631757, 748581576, 754922569, 585266720, 659208872,
            972775938, 293744351, 100636542, 159423346, 566014391,
            330543672, 781438044, 479941557, 376713066, 442155060,
            570864894, 582020953, 903013566, 559291572, 748599225,
            404915916, 828083779, 828163147, 286254542, 3090422, 333134400,
            533678088, 863516897, 693237240, 548875418, 427073406,
            997138234, 838194912, 296107400, 57814372, 684493427,
            148967887, 201198099, 734929611, 942045228, 321561131,
            427365176, 105905751, 667071600, 538248441, 829216116,
            20939322, 718013423, 647806074, 642734085, 829781419,
            589099712, 238101022, 798061753, 69196771, 92510124, 367274830,
            399721866, 422354518, 977511395, 938299155, 684985110,
            861149839, 781253542, 670014476, 251121275, 622751338,
            909729618, 16508229, 873156942, 989306579, 548282057,
            518485877, 181948999, 880985524, 630164015, 680958316,
            628584104, 350745119, 763813260, 694954369, 939234310,
            678546127, 651116160, 834564099, 819523809, 215693732,
            565536855, 688990748, 665831858, 249991317, 939818587,
            56653150, 644099589, 955543994, 318401289, 175240313,
            956501594, 750474366, 856721683, 256253624, 616835044,
            826928665, 37191030, 612338786, 121645389, 778120875, 14069236,
            269208598, 402072427, 439693048, 132984906, 873952519,
            296768883, 12099354, 139554330, 687111985, 669708160,
            291684465, 117058996, 344212075, 904370996, 866035938,
            672354450, 684550909, 856693095, 973882459, 969729099,
            548022831, 845860890, 680766885, 818506095, 281217762,
            656191027, 569832328, 955492068, 559132633, 723209824,
            512912833, 678935964, 930762366, 922373368, 830970985,
            269880455, 240874766, 507549537, 206697816, 958045762,
            858739752, 613956315, 668660111, 953548659, 165692494,
            889693697, 913133092, 70913619, 610486558, 886360087, 3410196,
            642425913, 304531473, 139845524, 22095728, 137293405,
            926598285, 306753744, 390609358, 440591939, 934433042,
            918464079, 135057640, 91116869, 927516966, 103194786,
            975050695, 502665611, 30317100, 668067967, 39418902, 404235083,
            427568990, 568166371, 393599595, 32799921, 932763029,
            775114077, 925978885, 184769542, 723881920, 666042835,
            411789601, 904131748, 704351658, 938147583, 563391853,
            443220844, 888616553, 847961806, 404856301, 971426314,
            716480883, 9177357, 584397216, 910259512, 658216876, 852020878,
            493298194, 800389481, 965736461, 218213811, 268873217,
            728598704, 771315924, 685666864, 340061787, 596267533,
            101821350, 918053684, 143757053, 545894049, 245359933,
            591485920, 443888669, 805924866, 83247065, 538215636,
            796274137, 15708564, 363650537, 503641833, 485747694,
            708611052, 366180577, 517944520, 448770065, 10569562,
            433692769, 788326681, 40117970, 756387208, 38507405, 90282859,
            392045670, 190935046, 73677618, 467884169, 599200684,
            757726258, 418701946, 311555711, 9994310, 989653532, 273368444,
            626893670, 275957627, 308517942, 743839137, 313009300,
            664162673, 271685014, 427814823, 577296619, 380895811,
            615358126, 715737923, 100698291, 135463334, 145252675,
            884203323, 996786844, 278266448, 331938412, 437896822,
            864151456, 555432984, 128153963, 643093791, 351551709,
            950898973, 871298963, 158394876, 833648830, 438987447,
            548139677, 268294084, 953351725, 740295589, 829873317,
            535768984, 180710201, 670554395, 202891032, 749335948,
            447739266, 779299940, 616225969, 8465499, 879400654, 540461466,
            887900140, 655876352, 751515151, 990437173, 695140956,
            295610384, 514055149, 450103593, 634571976, 28370506,
            407886634, 531873833, 501011622, 307271272, 275248416,
            694710936, 237547194, 158431695, 546725418, 357956623,
            23266589, 142969750, 201527376, 684557459, 998812055,
            412808859, 777425363, 884383490, 615618141, 813675330,
            309507170, 48064059, 690667266, 925934744, 859141431,
            940197012, 742975803, 437841835, 927552048, 4865571, 631205764,
            488347195, 270150835, 774672674, 158108959, 451266505,
            179144693, 953652184, 317743471, 540199357, 626637776,
            898142835, 212856013, 20977215, 957477140, 984591783,
            875366288, 114946964, 628518257, 381137796, 929597754,
            669311080, 1132906, 672340422, 972951898, 509067904, 123541178,
            453434162, 83087794, 554712704, 683004331, 278057343, 17377781,
            559879273, 756193925, 802138447, 949191771, 634509927,
            614014860, 775592598, 815669334, 557815992, 206156646,
            558235282, 835135750, 888938333, 368725966, 223794494,
            402594685, 587017871, 853378328, 605173686, 53064026,
            981781220, 961396767, 249699328, 473721946, 786806961,
            666785686, 945278514, 111463441, 717971611, 369171543,
            285934224, 203008304, 236261452, 7590793, 678528858, 243480052,
            409449973, 964841268, 913792888, 272300641, 999336834,
            211502894, 85259221, 848972805, 569965656, 191952653,
            163300349, 441911198, 964030360, 132793961, 405955221,
            741868312, 935915026, 389153417, 107985343, 491466597,
            255439119, 333338784, 988517417, 567851657, 954845811,
            711033431, 149265624, 840245290, 182359283, 192500310,
            621368313, 578415151, 602184484, 310020871, 559086847,
            116400542, 692564775, 769026363, 304092377, 864683169,
            822123145, 467113451, 810557344, 614880856, 916547829,
            254012131, 72971839, 796274166, 557240171, 797344549,
            244662406, 985379348, 558985352, 247872566, 673789621,
            997956122, 47012130, 428361079, 409478458, 557350765,
            129452550, 305381568, 109747305, 216271424, 754559360,
            603168607, 464449990, 925669500, 961778668, 176787540,
            922623134, 1428073, 831086203, 307385161, 655041852, 892346987,
            903187641, 250552246, 999265272, 516133488, 778858020,
            398671712, 772969043, 755751489, 404475059, 359346398,
            798705930, 193997686, 636233841, 649481143, 494313972,
            222991168, 278372765, 823245395, 260314793, 759171702,
            194873484, 530142782, 887108327, 488773407, 945081660,
            306319388, 51537730, 789668038, 393173343, 429369304,
            128056536, 47489193, 517781647, 962140544, 752000417,
            715584497, 511590824, 231190507, 136578026, 646629203,
            390898944, 862557496, 786838733, 822478036, 663235960,
            256289397, 247956438, 540076908, 108092325, 684248052,
            379094660, 507712266, 859024378, 843013153, 899863575,
            270457763, 123859897, 451233872, 519145231, 815934131,
            963339074, 554805993, 385536311, 197981636, 737080927,
            107075301, 648441619, 981711668, 640360237, 275357085,
            697196274, 270859149, 703808585, 456261569, 27022616,
            368889541, 653929025, 457431047, 877048000, 867670885,
            598989667, 103642983, 445239343, 959158326, 561887506,
            58907475, 26953238, 90576995, 701694245, 423699771, 565781951,
            648702469, 568644156, 353798576, 383525363, 755849723,
            781857154, 673153782, 822622349, 509557371, 683108674,
            976057192, 317118290, 691602841, 174742753, 884971118,
            608868860, 944559605, 251103518, 795183438, 145115504,
            476427193, 497606682, 925219466, 268907030, 266246002,
            348666655, 381414469, 103679283, 35873475, 714639569,
            182861409, 507139571, 100546702, 933172699, 334472096,
            92640226, 912236718, 125654182, 153810746, 234675602,
            322849095, 439833817, 199328135, 352944834, 766797911,
            988727058, 821056657, 532181229, 290466305, 16383685,
            156594092, 962247549, 639822235, 887500128, 224446430,
            971922628, 791220038, 849077883, 122550792, 990224354,
            438910083, 108309929, 835066622, 683544581, 234762146,
            430847565, 475021501, 546015430, 25613014, 236322454,
            634951482, 71043314, 18709852, 87142076, 394767217, 732770741,
            283236478, 838534333, 334601686, 930188284, 676977002,
            153139893, 685318535, 239345929, 812315276, 2086473, 47738593,
            638352408, 69974174, 611227843, 929188292, 255258971,
            463716091, 956527856, 398337381, 899837113, 346845681,
            67966280, 616522899, 326826887, 275522472, 695721308,
            751641523, 341768351, 652486004, 136773257, 132111584,
            510924394, 230620746, 646315597, 168123932, 620247104,
            273039150, 60167084, 771374849, 585280602, 448382144,
            263888327, 907406352, 969512167, 231544829, 184989495,
            572663928, 209965465, 886421537, 479839460, 988062471,
            884707965, 855693876, 153088593, 349842699, 840747316,
            910790842, 626017528, 288821644, 369809785, 655829214,
            220970264, 14131576, 90464074, 856536961, 970681319, 375093344,
            369207128, 926601753, 177868142, 222819900, 96984774,
            879069197, 183467260, 700148048, 537260470, 528631387,
            176450852, 278299769, 106280374, 429431151, 861293131,
            829281871, 895992685, 906255970, 9413105, 614647271, 753300304,
            523766886, 192167257, 41822220, 657557956, 4261842, 840572736,
            210843487, 656776278, 870792668, 670539088, 79026563,
            849068981, 819229476, 474181363, 154992236, 282179908,
            571983411, 266156531, 41720980, 918411546, 104139268,
            224381767, 446936451, 33688200, 595577037, 590393818,
            230097198, 949913499, 99769738, 343759158, 19118521, 927487695,
            439331512, 11253667, 862792176, 261160786, 805728172,
            593255773, 160735384, 855158118, 405561369, 771916720,
            858378265, 74619324, 980183261, 508169607, 312318655,
            416645329, 223226268, 276135663, 374341400, 81230898,
            468219853, 818816821, 342448220, 362465196, 192334308,
            83061994, 251157375, 78502741, 631794490, 92392862, 387273150,
            579325498, 113480423, 615813269, 772639857, 56711440,
            897955711, 872049210, 377434155, 510894828, 548753307,
            190124957, 54117415, 795039837, 169170137, 451730956,
            660518755, 538976965, 460828233, 310054688, 130441643,
            316325255, 332615657, 4413, 896960404, 185559597, 223689098,
            929339777, 633415958, 482902592, 244446940, 942008508,
            594096207, 565240379, 71734820, 450458918, 289405071,
            974875988, 931467408, 803997756, 870736010, 942195354,
            51029598, 459031861, 30073661, 344351804, 144410110, 964467958,
            205952903, 531864811, 170108417, 686917349, 447362105,
            113118709, 550309839, 287271187, 196642279, 111193831,
            920317920, 66184948, 257165377, 100222307, 166610146,
            248292311, 563291316, 518447128, 406067245, 212788603,
            914896454, 538757734, 72460235, 663417414, 389956117,
            340253491, 24650934, 993000365, 425925248, 984058168,
            244940564, 688852753, 734374658, 239455133, 70088477,
            595145563, 250674308, 84162421, 839708662, 919118981,
            810133626, 19545284, 911920254, 233250030, 986901039,
            118609404, 703270770, 769297553, 674893788, 517831387,
            128515706, 646981439, 448099869, 709771324, 865210100,
            512198464, 639625392, 735992431, 969179766, 741967385,
            515117707, 558495842, 493330426, 350673242, 79421329,
            723076191, 217992419, 116155087, 745936214, 556321399,
            165768191, 538652385, 820879677, 384460853, 207406630,
            861148048, 714173112, 931887424, 407037882, 576071779,
            173224803, 384472336, 239292478, 595634617, 102648187,
            687379411, 111510000, 407088546, 927044263, 761430500,
            217642256, 141748779, 630432837, 307776472, 85652072,
            902763498, 66354635, 245042901, 630693402, 861522719, 87792309,
            30936493, 547238081, 882265890, 542612997, 250248506,
            441098966, 123282295, 573250086, 149470347, 880654561,
            26010556, 488371087, 728522002, 202706265, 113553573,
            569617422, 222852622, 15481199, 414268491, 384281212,
            148245297, 592908198, 60836726, 973866947, 267524277,
            634866675, 94802012, 611543647, 245359522, 658080505,
            795313062, 514529419, 555565097, 531873769, 992537383,
            671113683, 810111161, 882368097, 205131252, 295878312,
            173432103, 56446480, 227852771, 994212167, 913656925,
            290362534, 436278064, 873982709, 588585104, 731911440,
            69904677, 282330895, 944879568, 42808722, 798608890, 147124433,
            885430565, 280974743, 195211418, 13056194, 331969782, 48758916,
            996969194, 877852504, 473481328, 656772567, 536394716,
            939262768, 423979706, 752314370, 725544036, 393021954,
            388508761, 582908284, 171859706, 722895717, 569553785,
            423161930, 163709060, 80126497, 884452744, 555223367,
            733491958, 822814415, 743915681, 105421779, 436715236,
            582174947, 378089800, 641034645, 37001869, 156421639,
            421560265, 276858287, 9288397, 186416421, 314199198, 619878781,
            778994049, 539555068, 334551249, 885820285, 720732107,
            857804318, 519279959, 480473843, 148569512, 638317551,
            155096129, 44545137, 630825866, 79984649, 517800255, 122858074,
            387700097, 66375117, 522702098, 593117867, 504936088,
            510436017, 733049740, 615157867, 656485765, 634982164,
            988819851, 869427643, 456396586, 62562486, 56387455, 915283561,
            719679479, 510748418, 132696632, 914404963, 911617311,
            714050126, 109113697, 775004539, 405461870, 364609740,
            664716068, 57682407, 353996230, 361411000, 497174935,
            944092352, 181378494, 770241510, 764509712, 689154885,
            369529583, 784718862, 120580444, 919220408, 795098883,
            965719178, 744367336, 11124734, 234636053, 905279168,
            967526031, 55384691, 395237790, 155989644, 592174548,
            695157035, 767527362, 624183296, 825412364, 791994157,
            312522653, 532804900, 591006106, 666008230, 285104704,
            139345461, 916959484, 468969159, 430923999, 217931227,
            160229186, 55602149, 905369890, 934407746, 376006752,
            872358679, 161274124, 948836334, 85438166, 392225827,
            620797841, 306720613, 825855914, 994591302, 191203231,
            659570843, 407608411, 174395770, 496762228, 681841565,
            939711851, 977973491, 208993685, 672331999, 411745694,
            325740337, 339462949, 343190655, 364839882, 825814954,
            977335618, 688429887, 1102496, 420335527, 721799430, 998981435,
            590201875, 106095989, 573601693, 73544433, 224444349,
            800050427, 561926861, 506070849, 579858896, 397762411,
            544075757, 706299033, 368794559, 689770156, 592061560,
            447891130, 579877405, 127557366, 659334015, 838953374,
            302016686, 193907979, 39203050, 216643752, 937110765,
            659140041, 451621242, 629591097, 480109077, 990362740,
            599089186, 461197876, 140552195, 870084602, 722047166,
            152202964, 615136572, 611384329, 173159442, 95691823,
            924150247, 918735966, 713776701, 85606744, 748509356,
            124965379, 464718184, 100335115, 777011923, 525862556,
            546049101, 720638473, 774390894, 231522483, 429512857,
            376650007, 271741127, 548642494, 325939555, 388075086,
            996835442, 202794293, 407549942, 602978929, 349004012,
            843790474, 808734486, 653981312, 200246271, 685507507,
            284998800, 392154748, 771514099, 956068273, 374547833, 4776734,
            114491586, 99057597, 561948676, 292328112, 193112504,
            700095216, 820592730, 618911451, 264571845, 809549655,
            353458928, 236463739, 278455993, 795405036, 730783407,
            239820825, 793666600, 795094747, 699085419, 386898276,
            33531367, 788854929, 386959121, 172559496, 417669418,
            562681175, 60993429, 657765382, 898354914, 688352316,
            946301823, 755141678, 357444297, 722488197, 33899619,
            530069644, 493902841, 849621593, 31850448, 518646771,
            924607376, 536843575, 179789505, 208386449, 221017906,
            517816686, 221235218, 944752358, 359608402, 454598081,
            40301624, 623670845, 307774217, 178055539, 389481601,
            493552851, 783788413, 272273098, 193762161, 318981033,
            989010585, 796825574, 973401836, 806546998, 246490829,
            657067223, 594258051, 840769400, 438793385, 799457236,
            325415608, 885468627, 391208532, 595690051, 992648069,
            784306237, 166585738, 240289714, 248509410, 198986473,
            121225560, 800622256, 330099539, 809428661, 101109175,
            646126837, 234623632, 982603216, 324815701, 546728975,
            905000484, 933246248, 626516637, 24691086, 925112267,
            518998065, 849221682, 690147918, 998552509, 677930580,
            404176498, 878872271, 837458939, 24774255, 255975977,
            384461424, 135640461, 818457173, 319532966, 612044694,
            209411289, 57993207, 618006969, 503710563, 990264969,
            832047659, 564217280, 708096529, 414175942, 496449500,
            961027449, 52972673, 656909978, 169408896, 753253212,
            548080179, 445409920, 90887614, 263804523, 170529149,
            906515049, 130392497, 992064173, 712985816, 931226925,
            906928148, 460442067, 490217568, 288040941, 300365234,
            926913643, 356793178, 176035600, 42002990, 719365648,
            790033253, 919039683, 398701847, 574187748, 818368409,
            568268316, 24688788, 471472704, 320700527, 695178593,
            648405695, 969308628, 971428261, 212338944, 804592652,
            501254886, 491527632, 505608799, 260542570, 132290748,
            380384018, 781295090, 57833150, 335085869, 390545384, 6104940,
            100211192, 22450946, 909316937, 661958402, 118863099,
            944544778, 885723293, 487046532, 955145586, 377074260,
            342500440, 40938158, 302452014, 908343371, 857942475,
            936730507, 846394038, 682725948, 961691199, 630625220,
            178805549, 378891406, 161328128, 155221646, 157090562,
            228149203, 559090397, 663188808, 266133057, 135124050,
            805232873, 223349464, 619208, 846764883, 573487357, 350752667,
            25106015, 148178272, 686439734, 878405352, 324010074,
            915685728, 82987615, 976852612, 789896462, 769061663,
            498924339, 535058258, 452853752, 678559818, 266103465,
            831407693, 535494096, 240622716, 830690047, 194315135,
            197813019, 377087174, 590897374, 780912097, 285642285,
            707844707, 27126220, 453507317, 538294285, 577854623,
            917837085, 151083719, 353293110, 411094173, 710013676,
            713195447, 64039119, 987470920, 666940753, 739026440,
            351121599, 968775609, 935397138, 649296239, 891745479,
            466907697, 760511523, 828388298, 812487672, 43943315, 20508834,
            371340739, 127093856, 495219705, 342602251, 886716414,
            80314981, 90238865, 186594766, 962735890, 272992259, 352606940,
            990740725, 83226242, 857954179, 829594876, 893359651,
            891064476, 249354594, 603350856, 999593495, 310430216,
            100255712, 697676024, 696134828, 496458089, 556459834,
            682450980, 701419561, 999542715, 667167329, 872287705,
            303147739, 672078009, 206300920, 496598371, 650944230,
            689010659, 516112878, 757372857, 702383830, 351384996, 922047,
            27373899, 333530293, 767906730, 355119873, 59502723, 856431431,
            948982776, 371858365, 204494797, 551971401, 988842151,
            239565842, 893353287, 958374561, 173934966, 251041866,
            747220705, 122552430, 402008249, 771363817, 868009061,
            945828947, 489309941, 698771586, 366665074, 902612729,
            651264091, 908838284, 856380417, 603125677, 865543391,
            347072793, 302783327, 977745305, 651984354, 454619954,
            808542730, 277505178, 231143122, 514858405, 583538799,
            655238172, 907219180, 332610537, 325734016, 130349121,
            553317983, 398822809, 532655170, 581345645, 228716177,
            603099534, 89126810, 306100860, 856201713, 783147368,
            655842988, 39896755, 816393190, 432163389, 588649409,
            686684939, 602198079, 224826916, 267191151, 383007439,
            147435684, 494223082, 179018090, 288874040, 52830930,
            256694491, 401986312, 239270201, 586961659, 599341396, 6341167,
            236457427, 990995183, 775264485, 751509786, 258048332,
            92660211, 54967696, 101044073, 152300411, 550403977, 319964575,
            819581394, 100143685, 250719326, 575671458, 363660685,
            17466616, 354447805, 418955743, 542265406, 72200328, 734132090,
            522449893, 604215696, 530525108, 820065641, 752873079,
            829795959, 738655428, 322959540, 284492928, 988391367,
            577580980, 504611111, 941326121, 541979779, 44730969, 75058046,
            455682735, 776709829, 968306520, 842059411, 710953343,
            937279181, 56276067, 868959590, 501981729, 333679581, 72054309,
            722029447, 109731739, 53274989, 344712081, 568694785,
            903399303, 770817647, 286924708, 196182879, 279343760,
            609261144, 149673150, 301403029, 199436036, 935408834,
            123280843, 417545376, 74905601, 13591641, 277896853, 179305079,
            546233334, 983727877, 109681, 757716378, 298131662, 639579365,
            875346981, 963318014, 364216384, 914616900, 113286508,
            712695425, 405368275, 173575307, 561492633, 454177085,
            151332400, 968888819, 794691482, 544311109, 234592858,
            367276599, 594419843, 325984568, 231081636, 306078461,
            601446149, 209476778, 795053400, 375384840, 270344826,
            995058571, 576609209, 491397325, 639366829, 840796730,
            326408491, 446040976, 807953583, 638144231, 640289947,
            692233606, 567445364, 326641420, 589397108, 681507183,
            552896042, 212839057, 689939610, 943435141, 43826005,
            783702647, 21919911, 314380788, 667021327, 830964656,
            114016891, 590859751, 422178203, 503568206, 70507827,
            966989063, 726505711, 57002571, 379595108, 169194740,
            471386144, 734741682, 83354009, 562892662, 247416362,
            405395485, 484472574, 473623544, 336327101, 258680509,
            958607812, 518114577, 862856887, 622754587, 908328816,
            739736799, 49248761, 798687724, 874267403, 888568609,
            781701943, 807504994, 145288186, 930036406, 312498813,
            13090948, 629296940, 881049169, 708501138, 925130146,
            562472934, 829799882, 396041789, 654424913, 276702866,
            352543814, 263850533, 273788986, 446591681, 305289704,
            739384113, 253596836, 358053659, 11498508, 139509183,
            313058725, 860535630, 709553745, 557762554, 955004648,
            293111179, 665192357, 930338411, 797898474, 830573218,
            323980090, 922055388, 943191392, 968204453, 91819835,
            150924455, 955974814, 740590229, 707134366, 619532341,
            234537548, 864038272, 316400210, 936744551, 326110127,
            706153532, 732050955, 657002233, 302621651, 149735193,
            251813899, 469018293, 714894861, 772935963, 284207250,
            311403515, 586338302, 824286711, 153541437, 713086238,
            152080515, 921736816, 782699455, 607283243, 538759356,
            251947276, 966453790, 893688954, 858439863, 626731410,
            586622959, 774697904, 259916172, 653023089, 534133340,
            277162096, 120592304, 295435959, 209381059, 836959142,
            309772930, 815693631, 948943765, 854754458, 799955230,
            889116539, 293502909, 866691699, 276607484, 268320427,
            469195399, 25258231, 160847068, 250107535, 672442370,
            265158461, 762430089, 105126247, 255516377, 90168639,
            618941714, 150828931, 815201645, 647937823, 340379560,
            435581067, 273519451, 672250722, 75970872, 808490494,
            497413463, 744190581, 42185493, 650006083, 794311340,
            321344732, 954364175, 114650185, 374259632, 427689563,
            700280996, 12611719, 508764256, 936017947, 64336783, 258122096,
            543897975, 492095104, 315411281, 422713930, 167316247,
            303888224, 921873073, 33440438, 187862864, 316078563,
            504355664, 569044187, 503765557, 821634486, 383462766,
            427254693, 587059372, 777274478, 367645507, 783707674,
            452147789, 201387300, 453134220, 733767326, 941168166,
            756591863, 838671337, 791384366, 492461306, 386805810,
            940772811, 374002563, 305304197, 357607813, 199696916,
            467502752, 334384988, 575673813, 25055791, 637250638,
            655812532, 598627040, 737081130, 106959961, 722658390,
            349126309, 151780063, 3958861, 963883816, 330380067, 900246502,
            155961514, 98228467, 267255078, 733139899, 702782535,
            381780108, 156476267, 943089592, 528728439, 923925630,
            374298166, 501576683, 863844623, 603519479, 386865747,
            154217331, 388384320, 492869943, 372877432, 167451526,
            575936403, 977260960, 633954140, 631766289, 637929155,
            405365865, 199670131, 953039126, 743582794, 299465086,
            811438032, 748943447, 770579180, 834165490, 935066249,
            389445880, 686735301, 133832236, 594820407, 826068417,
            783681891, 58659549, 152849811, 324766169, 848974681,
            813493080, 349499267, 801627524, 29803723, 732188758,
            957877900, 536175516, 100950574, 354193629, 487009192,
            766252540, 227633639, 182443677, 906246606, 371386102,
            394579742, 553531440, 29069381, 770439979, 107546963,
            284822817, 379221013, 16128356, 207622668, 686403096, 93080123,
            44711880, 145017110, 810448916, 376645536, 160846600,
            474835882, 366740139, 242206926, 936771627, 963336208,
            641967262, 60966425, 159985265, 41434464, 531161275, 841139339,
            628684777, 729039451, 393776551, 765647068, 886743260,
            494973505, 159149106, 194136240, 742529787, 999469255,
            307788162, 105417958, 19750511, 831439544, 373262672,
            930914268, 759211899, 507571068, 847448333, 969202374, 1579925,
            940081576, 659692445, 110113216, 420526802, 426200310,
            419263434, 601847242, 139687739, 56096896, 587248323,
            854968890, 514298629, 738197667, 393408401, 127727773,
            692492398, 497390875, 713288655, 341138734, 597610793,
            401899371, 156245528, 473222860, 95892927, 742070098,
            114466143, 703827854, 221569024, 362743814, 84830758,
            737887325, 123118911, 110004893, 434826977, 774112900,
            570407761, 878838007, 622366082, 60183332, 245217402, 10504665,
            164547045, 597938172, 806747966, 155757886, 812101332,
            289175955, 71263904, 146516406, 579706960, 528573423,
            997449217, 879202124, 893109229, 426709388, 342981424,
            725150003, 699597691, 165142959, 861371706, 526576722,
            411195289, 708288293, 281595187, 677513608, 435885820,
            436198810, 793242969, 399420839, 997479448, 898426342,
            963529642, 691047011, 300927244, 626996606, 850170055,
            273191757, 338842624, 457391876, 930999623, 348609761,
            228683296, 925834016, 676434049, 783388043, 997315322,
            25678602, 525304721, 795606994, 144956655, 997122139,
            874421679, 339232093, 147085760, 744830968, 296147880,
            923653078, 13855181, 573447871, 340067112, 598474141,
            653975443, 672658709, 659523823, 465645377, 847030069,
            273864204, 144001550, 19603675, 775553668, 493384574,
            434577068, 289146282, 554546398, 83999805, 163308730, 87980521,
            956678076, 836888606, 931656052, 552143152, 384845667,
            955556893, 48573641, 716651981, 583352667, 471542568,
            347483018, 138134265, 982816345, 970837264, 141817406,
            369853066, 700924631, 198630097, 868474259, 444790520,
            82074595, 240060065, 341616492, 837230183, 434016581, 64415216,
            537081977, 761764537, 847807282, 571181416, 696164933,
            800245737, 274967474, 631302001, 278034286, 285821888,
            992745073, 846236805, 893896954, 848437611, 86612487,
            773914724, 733350683, 29151199, 427921268, 733518332, 48317485,
            506815568, 730515181, 241747284, 344206958, 593634230,
            908893895, 784691449, 467388740, 970012131, 264534148,
            165331302, 245673270, 294364751, 344111994, 281959704,
            268658389, 689865884, 935654315, 761242085, 556958380,
            534469518, 320471890, 482953747, 920389593, 831325396,
            754043348, 696327768, 593618902, 383477657, 190457774,
            85310252, 27865229, 764982336, 610904021, 169882555, 190778652,
            849315702, 923122564, 576311081, 25043341, 229158793,
            740893447, 704670827, 908308054, 761809672, 824638930,
            651026012, 365615092, 168357235, 405656972, 238014522,
            754738185, 710782671, 240565064, 408898922, 992593302,
            21146904, 380008537, 903677707, 66498456, 451091785, 344825497,
            53404898, 388946351, 758398097, 721043856, 69903805, 899085012,
            300128927, 947536958, 570541321, 7330102, 270349168, 790087694,
            261594175, 612756493, 94349204, 36878613, 957125215, 478770848,
            552120599, 697794475, 17277230, 723075518, 850967439,
            822528107, 670113162, 684485077, 336798497, 696383368,
            358170036, 634706216, 247917566, 135376113, 849938257,
            599384421, 713784741, 207816317, 818617451, 606956800,
            501772696, 559506052, 747720418, 669525308, 299472539,
            939416708, 384732016, 519400865, 509766773, 24145773,
            770137196, 42374001, 233069032, 174268023, 399560881,
            834876622, 742691406, 483581875, 105657156, 81173604,
            135429709, 794841107, 534433003, 219121821, 439132997,
            132821023, 617640389, 582855292, 760949893, 233284008,
            543995881, 32850722, 89559565, 579744127, 733897764, 552181150,
            228495986, 95412278, 219631125, 910567466, 370885560,
            113962083, 510832393, 985221951, 224113027, 524821734,
            762538709, 336895142, 668254192, 539952255, 475760404,
            835464473, 283459730, 494884079, 84744657, 395726053, 61697884,
            111828977, 6825957, 14993173, 996024361, 724656076, 381374473,
            651777172, 62699763, 188828760, 424324008, 998764861,
            399155949, 335572192, 812820889, 954823637, 777099806, 708168,
            841241932, 667737986, 226994027, 979326542, 73751273,
            990543066, 774528766, 645659515, 619621355, 447929054,
            158463608, 949001368, 681329381, 320028980, 478893788,
            140565193, 820411102, 88091071, 791096477, 688158169,
            358199934, 174179437, 149600613, 234928343, 804172116,
            381252223, 794813818, 293675779, 363858104, 989706560,
            111772099, 439972077, 698033911, 355750153, 396870148,
            604072442, 120198629, 349080455, 986821316, 357385766,
            99689641, 87422526, 125138806, 704584890, 868132750, 987796810,
            291242415, 49334788, 851267623, 284387691, 867101423,
            529313573, 170650341, 628327672, 598579035, 527199237,
            38539978, 264550788, 326679869, 352861091, 353542789,
            737770345, 355581930, 459857613, 374739783, 982274913,
            449107393, 817400356, 308093806, 61252475, 642017836,
            830692278, 645975324, 738339240, 98544577, 618589855,
            415069592, 701837065, 977328289, 920367474, 73727778,
            589033248, 710325032, 90974991, 261204935, 655480347,
            843554730, 763830434, 977922624, 745946162, 644099476,
            336008249, 18929545, 139179385, 713297393, 708909093,
            454488174, 948914310, 969414592, 751920845, 927248478,
            919912509, 271632992, 406046320, 480132320, 215858423,
            981176289, 853128477, 377295972, 177152534, 466790047,
            964193642, 922680015, 231965960, 638086588, 399312308,
            952886050, 735411146, 611563882, 203419396, 271876817,
            557229216, 472441670, 954602867, 854995578, 371647087,
            468923678, 493830072, 863843566, 230445642, 938941651,
            625845852, 56019362, 569664326, 371554728, 633357469,
            697200507, 883124330, 931691762, 384920219, 722935323,
            464905647, 356043354, 804545185, 907585603, 631930842,
            927762005, 39915933, 140135886, 800842673, 566532352,
            240482571, 217754184, 408916127, 511578566, 990880332,
            242134470, 485527192, 881287098, 987899449, 67526640,
            298414517, 844648397, 407934063, 118383905, 645543128,
            564415927, 793577837, 477251068, 397674955, 654714668,
            555497717, 640923913, 934553740, 116561549, 643898877,
            903226957, 985037980, 733269293, 525805226, 916130685,
            36649170, 465467233, 111163612, 799124264, 141208920,
            480157724, 447450193, 435513863, 906601877, 551834886, 703977,
            907854123, 99839585, 561037474, 762014989, 63130568, 41507350,
            485427063, 264632609, 956392405, 587516844, 512649663,
            641261024, 56984441, 389782403, 64290201, 1952758, 224581181,
            290768389, 573513850, 931747835, 447433198, 369483967,
            501949060, 215853344, 835492052, 626508931, 391897310,
            771196460, 321621122, 241970618, 903715397, 911663332,
            356723920, 272987016, 947591045, 276408342, 802744493,
            978933414, 861702301, 714363361, 8772753, 9869060, 530139091,
            681115762, 88487322, 73265848, 683808162, 386750376, 621373124,
            48516165, 482865396, 563626853, 295848617, 281892160,
            949371175, 105895379, 401878147, 720096628, 421303612,
            247395795, 405023892, 173461222, 183184800, 430808383,
            581174482, 287702353, 914654830, 224679524, 727820557,
            582996069, 111270493, 274425022, 574592600, 950601101,
            639252625, 63847596, 275902076, 840732983, 114552162,
            842412391, 234131259, 191322199, 210349648, 273190712,
            958780547, 852231123, 245464985, 584894386, 266998588,
            933175035, 293648103, 584919327, 223479947, 89321381,
            856848005, 493417229, 877128869, 6516022, 873541592, 666830143,
            743476489, 735103616, 937262144, 948267200, 731152016,
            52036359, 51578484, 117708623, 650621266, 994447881, 180523520,
            259761145, 2245601, 420475950, 469906133, 282830182, 380733053,
            657322004, 394542049, 575486173, 620431637, 180796080, 4908153,
            783366062, 682331377, 314692467, 429923970, 485803913,
            668730465, 272817299, 60000507, 966988843, 314034423,
            163166930, 893317443, 269217810, 395852350, 279414471,
            309671066, 182346555, 4541707, 755385337, 139980311, 886697920,
            28791957, 713710132, 653659011, 51339498, 132062287, 713619394,
            125693346, 462863050, 330778051, 661439544, 834044300,
            244110149, 586813111, 676410751, 37620532, 438706194,
            924959058, 261515174, 73734622, 603017355, 10038010, 552030116,
            948177296, 432894789, 835663025, 139080251, 251167658,
            152896023, 882869414, 495516351, 455403652, 131679369,
            963490228, 245648851, 351642999, 584286574, 318318126,
            985522783, 199524562, 286356982, 653032535, 421230400,
            238427055, 131294606, 64784298, 759083568, 590653394,
            375498627, 278817670, 884304729, 71703691, 170116377,
            254809915, 575236129, 501356629, 55873990, 494058324,
            897701000, 608229830, 122087404, 495349516, 723171138,
            446874773, 749731524, 54894311, 204663500, 774661843,
            837271208, 487944886, 337434985, 823691739, 438697746,
            362185244, 396075932, 844469675, 619272401, 685661842,
            778802783, 95580707, 320443179, 450872081, 836753093, 70396889,
            859835931, 975487906, 61233176, 210355686, 229666891,
            873432107, 121852241, 332794956, 870475199, 54438760,
            538462561, 277064390, 506516998, 641672260, 950695101,
            536276598, 405632441, 244149731, 56495050, 939352521,
            722684165, 680184647, 709220490, 324526026, 380856780,
            495389184, 273633511, 809930818, 128111799, 259459717,
            539359278, 302852140, 922157827, 280203808, 683039964,
            825166398, 963747745, 20758138, 712253990, 105234026,
            368212682, 535529962, 891089349, 730221224, 434430904,
            800352162, 712412012, 595389440, 871575895, 160005968,
            371738692, 185035903, 96427010, 556179001, 851472044, 88137596,
            100234317, 523324694, 465920608, 976700140, 962424412,
            77945444, 68254097, 108256149, 628494213, 24001027, 52437695,
            184993943, 222676489, 395676522, 184386383, 594152369,
            281683086, 178724404, 52190819, 609465410, 831403002,
            969349923, 802061008, 825854293, 674128329, 19619096,
            146031927, 763589650, 996679192, 650993448, 695971520,
            779359044, 925173937, 764910114, 960031405, 306830567,
            964982760, 547402014, 470516218, 423193438, 487140796,
            642180664, 290948580, 909372400, 802977842, 655024985,
            39340358, 608785366, 762399643, 860086591, 222121985,
            367938176, 79534188, 177422773, 703892099, 710820539,
            231813296, 816895970, 447942474, 771490454, 976131865,
            474689115, 280502773, 8443886, 269817018, 701385100, 57881728,
            754796060, 951238796, 580075766, 282891006, 700074359,
            851612730, 41578781, 693944905, 90104308, 342331933, 254954358,
            512332077, 956452294, 831217036, 763403122, 674118320,
            131488783, 373546897, 368981496, 277652286, 180901639,
            314647447, 448843934, 932788587, 986082966, 884299651,
            340798897, 846547540, 710922302, 943871700, 388323570,
            841391199, 870031753, 923371664, 51174257, 133203740,
            236410146, 983964632, 362167616, 282011960, 910458558,
            223597237, 392910320, 695282892, 870456388, 934577316,
            260167011, 859906549, 397500228, 301441485, 678574166,
            917156970, 344188459, 161957222, 222828519, 305801011,
            838175561, 2082880, 353632607, 499283583, 290309724, 933404682,
            859256427, 368015542, 711114831, 569308759, 149771231,
            942025808, 852299041, 527671737, 193284594, 471330397,
            24004156, 320760040, 79422019, 144371594, 84641346, 767440449,
            18975398, 717421544, 614824123, 963246355, 152251836,
            159550736, 74097470, 174742164, 374540715, 505406404,
            984091153, 723171292, 431496378, 146597905, 898474736,
            967706542, 34546466, 233733601, 27546995, 945756279, 886866015,
            508859692, 497233717, 411283712, 983606487, 125051584,
            59006220, 879416641, 869616646, 383179294, 846887258,
            544107439, 221830665, 326592971, 961194872, 336936836,
            909585083, 334138496, 845904806, 686355373, 873644529,
            649272580, 55313986, 85877301, 990023234, 236570536, 718423408,
            754590389, 637268481, 214292556, 622047341, 139647832,
            850201552, 167935756, 59357182, 89318390, 740479647, 353641712,
            948098082, 796442531, 705383397, 704071678, 426786490,
            786492035, 936143380, 285015108, 565450435, 125852237,
            451316467, 903686661, 210702447, 719111379, 943972420,
            605763684, 543371777, 958161694, 760292202, 173587440,
            273371050, 420310758, 605550311, 514555484, 738202117,
            756243740, 36809985, 642696109, 989166403, 290052451,
            477711027, 432633175, 636123914, 227026220, 529120185,
            467367783, 985906245, 607448684, 277327076, 648767286,
            957686448, 850272191, 336085905, 240651128, 852039132,
            263789781, 665920896, 693562742, 999530748, 130320430,
            705101473, 659482386, 856910111, 703096462, 260381053,
            564193126, 282303374, 694146369, 338807324, 45617175,
            407183233, 95419604, 655394023, 506253294, 331120449,
            230184181, 456674021, 932068134, 500957874, 937463454,
            806332975, 478517999, 891619746, 260453358, 412609990,
            997011907, 472516735, 488839232, 224283560, 220201362,
            662736423, 550588600, 186781532, 751463960, 161461949,
            583245230, 663545668, 415663708, 924408418, 85508551,
            462001955, 53917996, 456668170, 586629260, 885328859,
            717519377, 681619171, 465833047, 709806476, 58629066,
            189793863, 484025323, 422079811, 314939493, 599610055,
            673152598, 328501049, 936707568, 877843447, 936280914,
            376285378, 936205380, 271555142, 990169350, 267815604,
            276818191, 741946932, 833843848, 435135651, 728481815,
            55204026, 465480619, 440298952, 456089529, 106552583,
            817433537, 750844933, 841498568, 80600144, 742909904,
            300834658, 815956920, 976408852, 227213749, 369068567,
            151831348, 694598328, 169243606, 249244468, 51692646,
            953789550, 292521659, 494164500, 624629646, 496045612,
            699532467, 647522758, 79103107, 6479914, 853122420, 79957675,
            901587486, 638685817, 848234694, 35637386, 511993242,
            209383475, 169108628, 582914835, 315704176, 840249554,
            769788933, 978781600, 616909609, 65741326, 683099026,
            961186791, 967899004, 822715599, 181088719, 727376470,
            817459176, 400123560, 577913159, 247725952, 47593409,
            472593769, 56539749, 297398744, 989576163, 795584113,
            557993983, 474485040, 862828045, 199106412, 125434623,
            581057441, 144757071, 227604727, 497109810, 445860771,
            511645621, 173823011, 258042146, 260893383, 243053281,
            488142867, 270653442, 536423959, 380948708, 402012088,
            78878464, 565166759, 515379663, 698095962, 82329180, 652221812,
            969572495, 469898863, 916991457, 316394069, 941597345,
            783476250, 471516423, 678573324, 842502725, 869828584,
            475810879, 726112363, 373412458, 222880893, 731145569,
            501467038, 381204393, 613182257, 688429604, 407052349,
            873029116, 322249405, 596403021, 304378435, 806062249,
            261227682, 488155521, 791174920, 464967017, 122079229,
            283746944, 799151762, 333857027, 343765630, 889245225,
            457234623, 883425653, 866832505, 193323237, 607575580,
            671942010, 698071091, 50019314, 764671153, 801276189,
            432172749, 38352518, 118940391, 799004729, 405359729,
            888907771, 333335343, 802034177, 711537560, 373842498,
            345613769, 579408971, 237268093, 457976303, 490910146,
            256096687, 458387647, 151424052, 640421523, 91220091,
            662459726, 348754620, 58913099, 48110015, 202227017, 118156522,
            251780520, 699376336, 637442919, 687881846, 183017193,
            957483120, 662694692, 948589110, 841059733, 360165056,
            108131208, 600391912, 198899046, 574410862, 185955348,
            619324638, 858657506, 464344178, 100339018, 185333942,
            119548026, 921564948, 565960527, 63491939, 195999110,
            105715792, 734915078, 623454161, 592389432, 959747116,
            862476897, 40554051, 122335976, 45553989, 803619545, 117348690,
            85314354, 441949223, 141979163, 44698583, 236615454, 921932666,
            432437400, 189147116, 447790812, 902731896, 315387426,
            42222194, 296425665, 928251966, 665794909, 768480433,
            730379376, 143384991, 739578237, 563698751, 149078759,
            167450401, 556435027, 616697816, 314151264, 499127751,
            83130410, 401466221, 521965018, 876331405, 253547173,
            196747801, 591903387, 646311306, 979682191, 273860989,
            80514624, 70725720, 117298730, 641767610, 153058807, 818068045,
            634583804, 711988640, 828767545, 584867933, 270112999,
            876403527, 491920913, 32262500, 693584263, 131072628,
            583947970, 907830165, 454641471, 396052204, 406625682,
            711037936, 627503525, 437514465, 369047215, 451471067,
            530567468, 69211524, 102993356, 688070304, 158151284,
            806313233, 862056432, 634494264, 85693253, 940539307,
            948553373, 356906704, 97794842, 880121218, 557198461,
            516835121, 954669678, 317400003, 822599624, 49347179,
            157381715, 314124041, 72625665, 478541486, 314032761,
            136487824, 581226795, 600121415, 547651842, 632752169,
            224394445, 842041688, 48254392, 754315012, 968021215,
            405093034, 117676401, 576868277, 470566237, 221161434,
            286122398, 765742378, 619783132, 847796812, 243017657,
            345951990, 961969354, 180616099, 757547103, 793607300,
            785812873, 373438849, 564736540, 698229780, 753057252,
            917695621, 571136361, 909838081, 188195193, 655797498,
            434685949, 232115955, 611237339, 996036853, 228722164,
            645261327, 658218059, 161273896, 678221369, 130671705,
            308443374, 465243990, 885845859, 610786231, 614976430,
            907764613, 510186357, 335715092, 422649276, 835990635,
            188540160, 874457876, 774276194, 419270971, 495911844,
            541397397, 408926838, 763870516, 61251706, 38033686, 617713077,
            65793173, 762728486, 689037490, 89960360, 138894804, 728374243,
            610998690, 759045850, 259776427, 598630929, 177109913,
            622057370, 751683108, 873622702, 71335710, 633043964,
            165032689, 582930283, 308316446, 726874646, 331612487,
            599386175, 331768274, 616580296, 953608270, 450204626,
            790212095, 188440764, 346822390, 126724183, 758457868,
            706027854, 704319081, 497010701, 569078689, 817908020,
            745059301, 863565516, 750148056, 220040429, 601672264,
            173377866, 105539560, 381911408, 846439166, 523957949,
            73041665, 887633821, 804631735, 467705871, 714185032,
            359773665, 817392557, 692952919, 757051840, 992018035,
            232162758, 577756863, 351205311, 934406688, 697541220,
            174778105, 173584115, 169289273, 432541076, 222019838,
            573025042, 982830420, 7635913, 253418880, 988594309, 428479461,
            118058606, 400163804, 373760217, 255349992, 374663591,
            491944623, 136753124, 960808019, 647416685, 681801809,
            183864261, 561060799, 814261455, 168265878, 502497061,
            842534988, 536024004, 195155834, 845951153, 121274351,
            855490578, 945940056, 311862949, 861498500, 154782338,
            949489870, 253908677, 52754764, 178137290, 792688704, 90390734,
            457831327, 489236663, 689986423, 373350056, 148037721,
            420341895, 925028584, 280052552, 105890007, 385817373,
            895599185, 729706429, 571333301, 657059439, 409846118,
            413468397, 390106740, 352873046, 285422372, 639711979,
            137732476, 785905715, 454653419, 852510725, 998569988,
            329480027, 340332838, 414718130, 434260598, 448168472,
            824389520, 863519266, 798410016, 13773740, 419577876, 15398100,
            850851453, 990213312, 512513431, 166199608, 220329212,
            317499354, 819801969, 794512286, 705614363, 509568147,
            25311454, 167362078, 454712444, 10194985, 570791242, 395878657,
            696520945, 930725811, 536046211, 288587149, 841688644,
            716128095, 569795552, 8906199, 614613646, 362734177, 891994623,
            240695428, 727920689, 195304626, 18499431, 912465998,
            988043820, 565204618, 499958672, 898694803, 138575364,
            14441468, 511818987, 914301418, 365127230, 93189367, 992427644,
            598102862, 204274838, 730916425, 378961345, 36214883, 15218446,
            898094423, 409502492, 859924259, 394080265, 946316699,
            888875004, 822763970, 967571171, 740460742, 140504048,
            569278627, 386784860, 384016034, 826868112, 878477337,
            26910378, 893823236, 156692845, 776700857, 181694118,
            946835517, 164657414, 524937347, 565532083, 714308896,
            447623850, 210314959, 531180889, 828781135, 636551497,
            256123459, 775271935, 777649335, 169084481, 992094996,
            854940457, 453214506, 877083765, 708540790, 9025459, 782407957,
            554046193, 990757986, 65921763, 299321906, 822447023,
            200145456, 384196123, 909318833, 639208701, 629100262,
            262040423, 559084595, 165549121, 813225762, 745185812,
            61785321, 130913781, 913274010, 300823752, 572589181,
            138038646, 438221839, 494373942, 184347363, 317207423,
            669065288, 632877343, 997639201, 574077100, 267158250,
            934352375, 657739118, 213734397, 680183992, 933974907,
            239719616, 897289799, 197321358, 813864066, 339327854,
            955597410, 539765882, 512034115, 613588795, 90264862,
            965163179, 54772984, 838427105, 128340433, 634704593,
            296601384, 412261318, 442742190, 938513843, 645955885,
            428883592, 540376891, 65386082, 251358768, 137903394,
            205454829, 152404730, 600416491, 148914105, 374537229,
            46774818, 739184207, 378444075, 706231900, 953972283,
            370671968, 415763735, 353566971, 625031365, 853574391,
            641519477, 823509354, 400141391, 649952708, 835942272,
            886912370, 202822853, 693362525, 33490146, 821700487,
            170896261, 210943878, 191553991, 131626283, 48495047,
            444013775, 578873353, 882446530, 919639264, 300544734,
            853248268, 30065351, 715619363, 195187670, 113377330, 36216792,
            993609328, 473951060, 993534906, 489874163, 213278046,
            680342126, 624487145, 681054569, 168269211, 879438468,
            530954530, 740953739, 299037721, 153225950, 487391635,
            817099662, 577973948, 928988020, 649992120, 762796430,
            654795739, 104536134, 476596266, 867921935, 261737901,
            920518528, 649964361, 88498334, 679289649, 586516085,
            781048084, 769418553, 114179515, 295016102, 707262541,
            841826455, 473800734, 312903555, 699097896, 573546193,
            465994320, 539635663, 375896208, 791932984, 137368020,
            879520173, 739895368, 366422535, 728671693, 830518482,
            315062093, 165877641, 2898129, 671907568, 98859155, 175058934,
            925908541, 679275767, 879467129, 753988425, 310563012,
            569699421, 677898398, 895177068, 71662542, 683449265, 32981352,
            879504358, 785538107, 722363977, 900024233, 649167248,
            691890240, 704729860, 240935039, 319148369, 103022789,
            964449153, 207694068, 194779612, 856881109, 674030925,
            824676801, 13429813, 884616370, 178132866, 118802682,
            585803976, 177607455, 433947267, 951238396, 617718737,
            646885784, 830844393, 598128024, 810796870, 806198291,
            992002526, 360745127, 159614992, 188576248, 52450373,
            271038255, 724025673, 683932710, 317816581, 957470811,
            816480007, 296577686, 619820731, 415216193, 149908859,
            459052873, 86223079, 481772420, 911008497, 690982304,
            438561510, 922932887, 328924925, 309458230, 140542288,
            908491831, 456913105, 483366377, 18446565, 247669292, 58342179,
            520341821, 296233940, 730661829, 776948303, 483321857,
            315960708, 635771618, 482535393, 677912496, 378867165,
            914439453, 727453659, 983510626, 46727756, 380333377,
            312385044, 928957974, 419496566, 57465536, 85696321, 280128327,
            955796206, 992805756, 811748375, 621056152, 484218290,
            58889583, 382176036, 638591010, 151354569, 573297692,
            979686665, 898101341, 812999494, 874837740, 50758488,
            657956638, 87371460, 360442776, 994859406, 518582698, 77379233,
            428726391, 312115547, 340691468, 850550041, 28171319, 70171622,
            427204601, 976288641, 936184628, 914032319, 750920701,
            16533670, 990399521, 122798927, 705583822, 314934719,
            349784231, 581011310, 395070813, 933428699, 779133513, 2288655,
            762910680, 210071917, 366663262, 289713153, 197872053,
            206487637, 650958350, 350680068, 778721614, 395438053,
            84436724, 705859906, 55942803, 573397855, 678670895, 106696566,
            752273961, 795167067, 17634473, 819587062, 997273833,
            507568550, 6737780, 313333660, 658486577, 818674422, 706382203,
            215547716, 222756472, 527306445, 271005494, 504763274,
            680024271, 136166255, 934743321, 113039306, 564824537,
            825929396, 256659305, 895232282, 757980136, 467143018,
            281753532, 723040372, 906239940, 83613202, 819758914,
            259628487, 756045179, 675484592, 773181053, 308091130,
            895963692, 62223772, 726235763, 830477458, 739949837,
            676037363, 980258473, 255787497, 759997064, 999363606,
            647263997, 231441534, 970159251, 193442592, 419821724,
            536005859, 869356196, 560846240, 192594695, 401453134,
            473016577, 955098118, 432662719, 459463133, 917010926,
            829925734, 408464775, 148799879, 399944791, 288725472,
            613492469, 996551050, 829942868, 664683247, 858285391,
            390941495, 111315021, 862927513, 827556565, 198014776,
            379295027, 991422994, 859842172, 34864225, 235998143,
            491440878, 827562793, 230219679, 737928387, 103582250,
            767154347, 454959156, 551113590, 887939978, 945466859,
            668679499, 626972370, 170861127, 372892862, 161451457,
            180049197, 742717853, 251194981, 757118625, 221677067,
            718373491, 400048396, 147259963, 531382637, 526159530,
            688829288, 189018718, 790786088, 158805442, 207091547,
            723617250, 436837766, 169729945, 234079020, 213368510,
            688659405, 272455596, 634772950, 410245527, 966341547,
            736258718, 82222471, 744174822, 897049645, 410856047,
            990522440, 529822734, 205401648, 854442939, 380126083,
            363622256, 105961223, 704267442, 644545417, 601663901,
            305348309, 916769284, 249939922, 296469647, 57507809,
            880769882, 637456685, 859665754, 302273151, 589229661,
            114314078, 856679072, 395315451, 860534040, 999840669,
            986870539, 308952332, 751233712, 772006301, 336768642,
            535453298, 751481109, 846005259, 657094279, 255051183,
            775805566, 100086608, 414551034, 427427982, 514683455,
            55434644, 159860733, 461127846, 36030246, 316210687, 756419389,
            413837486, 542856992, 43108390, 178329112, 398187838,
            347142049, 759702927, 286067322, 956620901, 472924212,
            478271977, 897104506, 265395870, 83364123, 596027979, 45823430,
            391472055, 698686193, 494739562, 841815378, 470466167,
            505606265, 463137403, 496072994, 178216107, 606914682,
            404114997, 715981118, 587088264, 538760049, 271739109,
            319157945, 966457430, 531492413, 586607939, 551771273,
            964830394, 316075120, 726914388, 21294983, 612077669,
            656959801, 586962686, 887236122, 156327913, 896038144,
            954334053, 175961012, 711364243, 744344648, 695189809,
            613918621, 386632602, 419500141, 204498379, 364385544,
            259285763, 305654553, 329912731, 218347500, 885821901,
            439999454, 559009717, 68051287, 370735986, 406471938,
            819400638, 53468474, 544464109, 637872594, 701909156,
            583186431, 654311797, 959127177, 43164169, 121188013,
            259220087, 52438023, 990975479, 426052893, 456492109,
            936132613, 448524378, 396973880, 847914666, 604898302,
            141161726, 167594390, 127401286, 937649744, 446220733,
            214725105, 934006461, 61675987, 62170063, 117066069, 613570465,
            463573312, 565106067, 9680624, 538671780, 744188781, 919609790,
            54390494, 568924832, 373660872, 900913213, 317701102,
            457228610, 833350187, 494246781, 788179363, 743380563,
            159977511, 645484199, 898686774, 907908191, 26599361,
            226862239, 351727047, 67752206, 204815886, 761739583,
            449854824, 578119731, 505958685, 668429621, 805781584,
            811580760, 204534932, 200969913, 192786001, 840504632,
            629148956, 176710153, 496044041, 352469124, 668187532,
            878940653, 322843470, 381281148, 525571851, 534285913,
            893656727, 478414665, 124888561, 734682526, 316589951,
            121273372, 166634849, 975940946, 374984053, 690179720,
            979770069, 626275164, 84981992, 980346846, 194477398,
            735629657, 966133299, 990998665, 910361997, 668955960,
            30463918, 793110255, 736776434, 108085833, 36550632, 140895453,
            797634904, 621228089, 772458614, 580506760, 660297126,
            965563802, 564200847, 167133111, 657611233, 322753341,
            300497756, 925040668, 903233130, 667531482, 555459984,
            615532364, 909396385, 849820237, 355596902, 573874774,
            765978752, 578453414, 709514357, 595765592, 23595329, 96630476,
            539734214, 340455820, 767018005, 556888549, 594913947,
            333340639, 274289739, 732864399, 702323232, 703402071,
            355946096, 769818386, 754741244, 505500811, 46184934,
            695185564, 540997387, 923279834, 877255164, 62503591,
            291885888, 245228572, 210343367, 287836587, 551196904,
            810722517, 474422572, 232772663, 759283760, 843549065,
            492526779, 605853829, 635269999, 760824810, 837807465,
            27804221, 816532298, 739749605, 238620141, 724829311,
            343648167, 720634480, 314137533, 313599251, 386470535,
            554650451, 238852304, 120393928, 369788526, 953960397,
            987654680, 790195475, 319087733, 35343797, 522317480,
            399699594, 177247476, 763464749, 472353271, 397470438,
            120497594, 223739781, 695092952, 613139308, 318314642,
            834387641, 362473531, 545655940, 690363465, 112640748,
            512785592, 771070596, 914682004, 899075938, 675607194,
            888171200, 996697663, 733272451, 712550474, 577670729,
            170404885, 224309341, 163614911, 120793516, 509253585,
            307476913, 589645836, 688363565, 535072919, 142568193,
            286561879, 521974079, 715196415, 533901697, 419913033,
            747819589, 580632892, 23486204, 554145587, 171081528,
            194766109, 719928587, 611214703, 851154950, 15487804,
            814825897, 96688016, 118579867, 3775459, 233063848, 331817105,
            816348407, 816579116, 30611205, 553227047, 592723341,
            287172441, 350116761, 70731912, 632352068, 480895338, 42754178,
            401569301, 492589954, 113090778, 484455583, 107035625,
            454899578, 23031466, 475970094, 911051933, 185266207,
            872351383, 408579223, 395659452, 404003060, 123339545,
            423342603, 907051573, 276635797, 29138207, 508826799,
            859042231, 738436613, 814395303, 717032193, 444026621,
            847261465, 905779790, 849241958, 63398883, 667937998,
            668672752, 9508752, 328173221, 793595131, 458429412, 31742532,
            175481178, 148345967, 815060968, 873839625, 517523762, 3636370,
            939061033, 178275654, 538264650, 657009158, 527539221,
            553968154, 962547924, 145887677, 226756224, 885934660,
            215109410, 48079906, 832674764, 678369773, 300051142,
            115916576, 666307338, 78996777, 423695703, 919030182,
            471556322, 485090807, 515289646, 658732366, 112884451,
            691098025, 459342048, 886746836, 421460818, 568504799,
            182474413, 307345196, 204297380, 202099517, 594573782,
            562811909, 172658288, 470010072, 795171358, 215841633,
            589209898, 396894338, 694789785, 299163839, 860185715,
            286633381, 67091909, 893843772, 969919960, 602228961,
            280410726, 324501510, 193040521, 975110730, 413388642,
            816431140, 337777519, 196162459, 526836264, 305157385,
            993604571, 347195444, 307425903, 344307905, 121692802,
            587213186, 709154014, 837523650, 441174501, 975788193,
            452369487, 103211215, 220614098, 581009779, 932997093,
            547647031, 482607167, 50072379, 924651170, 725792142,
            646169204, 510072412, 993775457, 266001396, 482429012,
            400686872, 502726331, 938006448, 961635438, 388619069,
            776966465, 265334327, 313691356, 977664123, 932131928,
            111462380, 210305403, 900145109, 24605941, 176082982,
            464905026, 104083404, 169700204, 85293256, 342591841,
            476665221, 671639756, 408349237, 514857273, 742702358,
            451709327, 553709900, 879884120, 819078973, 135564167,
            424028382, 219075664, 303287968, 634618410, 280311758,
            917213105, 309994193, 720489408, 579139267, 417423938,
            800781214, 599640617, 505455249, 403684083, 467577113,
            227586682, 344196163, 735935725, 667784439, 459844430,
            30439898, 495925375, 324780327, 603832338, 61061131, 651321514,
            541303057, 586331482, 888221605, 263203392, 628937428,
            10527923, 659587098, 996759442, 517825375, 360413030,
            286872478, 84987, 913201049, 692879801, 984450495, 186738604,
            961191053, 976409324, 732197779, 213478428, 549640916,
            884150789, 37765378, 309483190, 325564458, 510856805,
            719814576, 773536658, 204689551, 958476928, 15999957,
            473758727, 149541554, 540785221, 380522681, 467557394,
            256918875, 78850826, 527052627, 587744301, 778892968,
            632312798, 265927849, 513169931, 383879319, 135269401,
            993135970, 21203874, 939852053, 166146881, 641173326,
            937480036, 720975490, 800641597, 846156653, 28870224,
            484434980, 448756933, 79317533, 454553441, 437745588,
            490040725, 925595542, 638397260, 782433073, 356744365,
            863014233, 97778571, 273470322, 749300963, 136482685,
            588897366, 306237337, 951224664, 292111814, 490880628,
            230015322, 633492086, 291476727, 407528949, 117583807,
            515288259, 71561560, 237296111, 818877983, 105330952,
            985477776, 285172416, 985466724, 387879882, 347652483,
            666587543, 102697214, 68559223, 913009779, 945967233,
            854497705, 851736355, 12694692, 646159525, 829467102,
            891033181, 867772545, 1394104, 536316921, 905554804, 973367135,
            866705543, 807394037, 139281720, 864875868, 553871938,
            774450094, 748262751, 649127833, 933664485, 178945376,
            92791950, 769174206, 705357613, 914136442, 378402323,
            617223095, 330012805, 10258899, 374530954, 208800360, 42447042,
            534898505, 563885324, 342010059, 435588241, 938727753,
            216504907, 515361475, 89768901, 221522476, 369478118,
            527507567, 863529708, 300163866, 7935630, 794854943, 834388364,
            493386436, 186896355, 544436214, 361322646, 90161782,
            186105454, 36315699, 305237997, 27361830, 446819184, 788500942,
            9987035, 502785205, 624086038, 928243735, 359409125, 710111154,
            934643510, 523741302, 951163789, 891562883, 386662167,
            956065564, 384085331, 340918340, 632729812, 93452399, 28316245,
            731901954, 497288340, 494920134, 176793144, 818519424,
            287416473, 759901131, 667019774, 609851846, 733483470,
            300202082, 341108805, 129444031, 143378043, 389115742,
            450107778, 337906668, 170654189, 279873118, 784069228,
            970769103, 256694788, 689528290, 463855388, 73714016,
            528118577, 663330602, 295935074, 390099679, 93817051,
            209741331, 737698959, 146620926, 602414685, 236875036,
            804589833, 776945192, 645205795, 828386292, 841620882,
            45210517, 998422717, 428377539, 349352729, 51593606, 999581942,
            506142201, 78638210, 929661705, 648270532, 291075356, 21077233,
            264331937, 134660897, 381806632, 443888047, 720292027,
            482845507, 568692440, 355157044, 962794476, 265218427,
            135388303, 390163225, 745299549, 785251361, 443016726,
            227804335, 940192694, 450849561, 664470346, 433231739,
            645933579, 64972557, 381988249, 210720055, 384147936,
            522063036, 86883712, 911747816, 45590425, 232071727, 208405295,
            497416155, 448041215, 282444285, 977528957, 251714895,
            247961239, 693660282, 321647719, 570294677, 305279282,
            560921628, 178887727, 525040452, 247853304, 234549156,
            437140893, 136820337, 930976187, 309863597, 922231360,
            835601183, 202473750, 610278615, 745730995, 804265447,
            342742566, 927258918, 994149378, 36735112, 882484059,
            133244353, 859202612, 376959383, 49600340, 935803563,
            498582142, 688392001, 146083855, 546207597, 978933542,
            230703498, 570229144, 607609352, 696383057, 414919127,
            252939252, 716588444, 210095645, 568652283, 27709471,
            794864761, 123232890, 9936409, 652328925, 407912990, 843016540,
            379372242, 229619164, 532949432, 222553185, 236383201,
            50896735, 737292429, 227006327, 470991074, 870539814,
            123107039, 745443084, 668635985, 50138266, 373180072,
            820856665, 226654455, 475971613, 16317568, 705703524,
            379098652, 84026460, 641785817, 436317880, 980232737,
            889136079, 198166013, 259065675, 779808943, 310059371,
            100871429, 858067242, 667256185, 804812418, 706813031,
            25328804, 309743636, 981480626, 762707565, 673194297, 75734893,
            807992863, 280626951, 172181414, 485686105, 19856724,
            220698034, 117819790, 386699467, 595306960, 978588456,
            314966031, 762735564, 515590562, 340185193, 34325625,
            608282095, 959097033, 85069141, 383704359, 479489331,
            510210227, 691560139, 145509592, 44750191, 519947904,
            679904962, 409576439, 193418424, 128378338, 758514990,
            895279882, 991750859, 658644416, 643106487, 167498541,
            128448511, 476469992, 64301271, 721570661, 456026078,
            347041297, 884075039, 795734587, 208312130, 103708861, 8537094,
            963270450, 74892868, 696844844, 864177455, 201483078,
            777443567, 85661411, 850561336, 298687875, 716562390,
            730655694, 313948428, 318437051, 362444568, 386630676,
            534763254, 225510603, 649238715, 728419482, 978830455,
            678706785, 40251681, 967220054, 729231792, 239259249,
            497936420, 855113136, 480994943, 682556063, 531776283,
            705558542, 186489147, 698147973, 124150293, 915065934,
            203720640, 246137205, 378431620, 827915671, 263356463,
            637216642, 950841203, 12457737, 786194615, 588123082,
            730520156, 325633575, 886619222, 897133771, 262091554,
            125519820, 209794560, 450796838, 698314993, 551188640,
            224049998, 636532928, 591199788, 844395801, 195150783,
            335701009, 166592058, 486092894, 43526559, 371488558,
            842331455, 107509336, 390255736, 551541612, 515049783,
            679102963, 712139699, 138604690, 738626547, 72059298,
            801698674, 80663461, 579030293, 918507381, 796953773,
            879082563, 736970969, 670186432, 447708819, 830801285,
            26328368, 915857619, 651446224, 538992587, 290232094,
            692094142, 838326773, 605510791, 965313571, 873167367,
            648013465, 160266097, 376729027, 27100197, 920916804,
            201064126, 112842674, 517833026, 450922693, 711013061,
            151268491, 280213211, 889430443, 760577072, 874864960,
            304783456, 729835709, 855634440, 656598757, 494893669,
            523310643, 476674586, 487941543, 762640748, 812861320,
            705044390, 833423459, 943103149, 997381786, 636860491,
            740424926, 483584451, 928955985, 406622916, 851348043,
            831516858, 232941550, 650404033, 232859957, 665469300,
            370785372, 350770518, 876714957, 38162975, 104412139,
            919928715, 386470315, 288914787, 874908980, 185757325,
            775585407, 296462999, 710002490, 113825342, 725679432,
            201171914, 968246046, 269589853, 287631943, 928555183,
            740685582, 81445024, 677952345, 161941305, 230412538,
            398979212, 888638806, 930498185, 262797887, 236928017,
            915676124, 152207954, 915593410, 545996618, 686573662,
            421299229, 101235733, 18955462, 450911293, 970806042,
            713208713, 317106754, 971492251, 574099181, 295962512,
            97280161, 750136655, 124788552, 899710415, 818711382,
            614077305, 997199812, 235899975, 230540859, 585353928,
            155886832, 200512851, 1684925, 453939450, 204319919, 590727605,
            585351527, 115961580, 782839276, 420005841, 385386779,
            903730350, 272561812, 617120693, 657743759, 765097303,
            383345411, 941145601, 169222894, 38566809, 543805806,
            328772650, 493814450, 902222807, 70816473, 922408466,
            353302791, 828417688, 143189199, 810098149, 640816681,
            914151787, 378011312, 956267306, 389752383, 786965128,
            501373341, 569541082, 936470471, 483644074, 971430520,
            602600137, 311798199, 917908098, 740649227, 324273462,
            709479959, 800445534, 54181369, 965170125, 590371073,
            255677783, 298094183, 367150327, 505050535, 616397489,
            755465383, 427814858, 933625998, 922788172, 320548605,
            924513173, 572267983, 534956544, 686807643, 247800999,
            163253743, 887653115, 231198130, 190483386, 307025373,
            346359645, 72829140, 472984682, 614783369, 734598953,
            310280238, 586437716, 551255804, 644112372, 720569079,
            527581809, 372168884, 368012758, 541500610, 677248659,
            325387063, 273615694, 45897481, 583887559, 662211678,
            938900035, 827078862, 916750444, 58308624, 540708608,
            598459671, 516781748, 934923055, 946860852, 503401041,
            377115453, 264369832, 334943483, 165045870, 940317301,
            68870854, 87412677, 123739286, 952466944, 695431010, 405468422,
            393451921, 330224033, 464022345, 794611696, 90956985,
            839622573, 873772126, 479982275, 710538892, 202108942,
            42844251, 17091164, 941091918, 589729409, 513885379, 943499586,
            1548596, 51577237, 287674915, 3501478, 986619067, 949553172,
            353859072, 958702842, 971429687, 440239590, 935158632,
            831657190, 740553867, 427250537, 842072188, 734868081,
            547223661, 122553478, 112103328, 75870814, 981470752,
            957787161, 124090716, 784600532, 742186478, 127593960,
            92377428, 388358319, 708397333, 725122386, 161189232,
            981320595, 412806414, 214062076, 266638673, 947086926,
            331570844, 250072233, 205260035, 764296657, 499758133,
            742458779, 315553111, 935736674, 302327852, 750396839,
            588830686, 162039668, 782305540, 335707144, 498899867,
            925199823, 437778457, 739239323, 696316486, 751921881,
            509373222, 986406906, 291221424, 855778331, 763428136,
            531424795, 268494059, 194346679, 54986416, 924639298,
            409493571, 826536980, 762152145, 481537914, 485452253,
            624641903, 401811414, 329365044, 84327695, 546960473,
            997182328, 104333747, 631597956, 621323947, 245199523,
            374307961, 956956572, 547383338, 739289111, 256839144,
            978903470, 43491263, 20135200, 438080991, 179230979, 456611532,
            790782734, 319513976, 131952207, 82831602, 700419185,
            321861436, 325842645, 678098742, 242201491, 635335233,
            112354304, 724982249, 315141647, 890475337, 941508943,
            385426959, 92045219, 846787927, 866152574, 965631792,
            224696333, 896737723, 787726617, 571460595, 878687514,
            278949384, 323084014, 846933476, 383111952, 303074916,
            145050872, 255043068, 757683464, 108526297, 357885785,
            935281311, 996519447, 824803365, 568817603, 467706208,
            210101195, 499564423, 153474247, 984078968, 271103336,
            708772105, 192316505, 490747895, 458981647, 943518408,
            132620114, 821074937, 70374943, 483971816, 879078821,
            962091635, 129251860, 297659685, 106098250, 180986748,
            272469658, 578388905, 676308986, 284292907, 899666913,
            99170990, 877321313, 402828324, 539670152, 883324209,
            947254075, 786011692, 666235241, 31888305, 674736973,
            962475091, 206078830, 935827450, 621168089, 436572332,
            308251383, 412683845, 997609831, 845580474, 668690288,
            257805170, 832483482, 622818052, 512994785, 269462723,
            200556817, 881617076, 693420328, 749962789, 253748697,
            238930168, 96404267, 770822981, 617704246, 778116372,
            657560970, 708711336, 982150958, 638981204, 690664193,
            185185948, 887218853, 133943640, 572448942, 495948965,
            490141171, 300649234, 461652600, 26855517, 931492199, 41875262,
            614069480, 35634644, 945929411, 741690599, 34264097, 832758031,
            619160367, 464044805, 408851809, 936719248, 620226254,
            914976933, 789585967, 689851023, 36658648, 812420688, 29479832,
            178607824, 608157812, 700678503, 804677447, 914621324,
            477128337, 352071394, 55329667, 551078809, 329383543,
            477771772, 726712755, 944474288, 304384842, 164957092,
            321554044, 372388666, 159968108, 115253519, 577032572,
            219943880, 635487194, 347483903, 274351845, 720187788,
            841473769, 841277872, 471841229, 633979468, 195769654,
            271474677, 143580851, 24822221, 927785098, 77442564, 396706528,
            29166365, 699157818, 166978165, 434165381, 33811171, 96907571,
            703016267, 42494128, 781623350, 337509212, 541276778,
            234614445, 344203334, 933076860, 187775786, 437353275,
            455108724, 435813022, 33834182, 723519917, 890317739,
            721260438, 350228249, 629664375, 601176686, 365081663,
            581267435, 272703115, 949406082, 90104096, 470107944,
            478553882, 153549194, 500720712, 791626780, 725410157,
            310233395, 131524671, 36105834, 883763274, 216536309,
            605032957, 901414120, 637251946, 974497027, 377779061,
            890029815, 704934222, 656710057, 963207741, 885582726,
            248231075, 687386783, 929513408, 834812460, 748725389,
            820995570, 188778425, 602454987, 359890043, 802558744,
            614917746, 437919496, 196429108, 743513142, 468360303,
            632086783, 244654691, 659393503, 56812667, 182212137,
            334446001, 510205032, 668119631, 279620710, 91938064,
            689355336, 23692942, 327670062, 13879062, 212491634, 448440194,
            501111885, 716147125, 964866391, 740860021, 107787628,
            370041336, 587052805, 650145830, 984399812, 563559647,
            325217661, 684882738, 860630097, 147194338, 601497032,
            665245268, 820953785, 44400741, 683746963, 984016706,
            431326684, 215887603, 190354388, 612989471, 553088700,
            559530354, 918309022, 419947758, 965119381, 762474335,
            799147254, 759503171, 589216246, 67615915, 62405649, 728352079,
            256775433, 371976929, 660769229, 681763961, 270549078,
            653320222, 271912112, 963417742, 115685997, 739872758,
            585067079, 304768967, 471417111, 490843906, 479854790,
            264327863, 934114835, 300861328, 941581777, 604798545,
            124369154, 836478720, 736341192, 689991433, 217417505,
            185006382, 557422860, 113340460, 160055749, 950030308,
            607978488, 443482149, 895359306, 77619006, 852176323,
            659268359, 25989031, 23361579, 403859507, 274560050, 227663366,
            786614004, 185061516, 514724383, 913149365, 978672162,
            45682707, 965953010, 45993074, 497938410, 5169006, 462217126,
            46909176, 308206833, 507706712, 840219409, 386079726, 13959295,
            458276024, 578631547, 198393012, 431975476, 302735028,
            338392940, 879463073, 29899947, 694225773, 808740505,
            321419544, 820723080, 496096724, 206300210, 130946188,
            24476066, 302647404, 780749736, 649810242, 953279153, 7229421,
            950027803, 4674737, 993184322, 800548606, 426149278, 299717340,
            249884330, 676486131, 452931072, 216138316, 493375494,
            472515788, 497190023, 904858387, 462403668, 111392923,
            733209910, 944362716, 170667433, 951919507, 594892660,
            787715036, 981660387, 476093496, 981617879, 411730872,
            837910404, 978322331, 559376746, 3128740, 418555709, 760416463,
            184418592, 972336794, 724488071, 114822404, 332888035,
            394137881, 123466730, 69500848, 723524766, 772892138,
            142086072, 485972582, 883912849, 398530905, 167218259,
            906637247, 839170957, 251163417, 899608496, 556936343,
            181166335, 622623407, 763453379, 44709841, 842059831,
            188664015, 584876662, 248381178, 898555489, 396645015,
            819227865, 391006311, 945127433, 478738167, 47582871, 89142541,
            784228150, 248466611, 876271315, 662013971, 131576928,
            722830153, 988856445, 584386795, 826820990, 178870688,
            335132912, 87929152, 40610569, 589743067, 99526282, 948861394,
            679873090, 674295785, 970622047, 501708876, 600715714,
            325368592, 744214170, 958550637, 247833110, 173115695,
            277526914, 765306711, 231537740, 680899079, 70576455,
            797660487, 535918542, 276069985, 788148856, 21130406,
            585098093, 782324110, 127964834, 643538277, 628879203,
            909181667, 437652782, 56053462, 223809388, 603752877,
            843709485, 55928088, 534414719, 354222014, 954585096,
            897585026, 594014653, 54694822, 994142924, 454387740, 50354522,
            670937849, 80704967, 313442366, 20182379, 408498064, 245448339,
            89111670, 454080675, 121979135, 902605748, 705708422,
            841627667, 365745102, 216148276, 801108887, 303489101,
            778477813, 621651126, 428924620, 811141923, 240279527,
            253452033, 450911917, 462127169, 897866535, 148670778,
            318935276, 278688747, 497550619, 817065623, 252654032,
            345934859, 939134062, 526097424, 941206807, 728665914,
            162032344, 36700553, 531478541, 955118924, 147493573,
            358683919, 852432015, 301600703, 345341021, 58431760,
            741989872, 776573511, 738942070, 102110170, 52857947,
            375260310, 786579054, 164650006, 875414595, 592817906,
            684926591, 322273908, 632542501, 773461274, 698149217,
            923377865, 981239387, 654556547, 878238102, 75816360,
            662532038, 219510221, 405012234, 735079613, 363127975,
            904713888, 29791557, 269302888, 669729678, 954331642, 69458183,
            276962087, 775613308, 633811294, 323071122, 104244935,
            774048798, 879402105, 196657210, 98914029, 675936002,
            804163012, 865722273, 283131721, 689596024, 383718998,
            703333011, 539060258, 846450582, 749608851, 452403317,
            323097431, 386770001, 168894580, 863786412, 954320557,
            240770033, 880009916, 102072398, 674035073, 300522347,
            574281992, 217797235, 953251669, 472267070, 778944788,
            984178094, 744239516, 552413810, 683604128, 990820713,
            692778004, 196593372, 900938515, 837984430, 828256623,
            421340872, 487800807, 428825183, 404420077, 729718247,
            461662940, 135269948, 947270807, 728826306, 505906665,
            806140489, 320937898, 717849405, 731548556, 677591446,
            569272499, 451632667, 430801983, 995127334, 532521083,
            296438526, 347098098, 898690063, 765644719, 128907959,
            26522692, 970656886, 407269555, 250554437, 309009992,
            991729845, 425279261, 392540854, 637504341, 707793456,
            441170959, 881150680, 253763173, 929298800, 829927492,
            611281818, 432425769, 669037164, 322708147, 136096547,
            659404855, 624844549, 622635284, 984936194, 542355724,
            695594515, 90236381, 296764883, 31768597, 11669, 725385429,
            872453192, 209001398, 625797942, 119229427, 825428387,
            948558161, 69197719, 581958237, 487370693, 698380709,
            143022606, 52541346, 66932006, 668542859, 379404989, 62821969,
            337599437, 987841779, 787050912, 744440548, 270840410,
            435233336, 411070456, 97210534, 13702377, 767932248, 634112282,
            167250798, 242713827, 761429007, 817670099, 819237943,
            642385962, 851748671, 189605242, 873611169, 290285506,
            88965088, 582955059, 670642272, 414612201, 346913582,
            954381584, 864980848, 374297879, 308950381, 903276330,
            92753668, 54797519, 357465024, 332760678, 854136858, 907320821,
            609641177, 405353584, 360774247, 365278282, 616892345,
            606735477, 919335587, 87407053, 783962178, 217876452,
            331025216, 637221615, 352242771, 556125900, 647032199,
            160789225, 340265149, 51974093, 817658036, 225891767,
            857881069, 629064533, 154674538, 839712829, 851354580,
            437971834, 288246077, 924561342, 232886623, 421221681,
            679967203, 272895963, 190397712, 334846153, 771602261,
            30550124, 573237303, 398629166, 134280354, 199998401,
            854614365, 639145259, 209972304, 256804604, 939509297,
        ],
    );
}
